ISRO2014-67

Question

What is the time complexity for the following C module? Assume that $n>0$.

int module(int n)
{
    if (n == 1)
        return 1;
    else
        return (n + module(n-1));
}

• A. $O(n)$
• B. $O(\log n)$
• C. $O(n^2)$
• D. $O(n!)$

Comments

The given recursion is counting the sum of first n natural numbers for the given n value.

so the time complexity will be O(n^2). But why is it O(n)?

---

Haseena Shaik

There's one recursive call to module(n-1) and an addition. Addition takes constant time.

So, T(n) = T(n-1) + 1. Or, T(n) = T(n-1) + c.

 

If this was the case:

int module(int n)
{
    if (n == 1)
        return 1;
    else
        for(int i=1; i<n; i++)
        printf( "%s", "Some ISRO questions are retarded, not this one.");
        return (n + module(n-1));
}

 

Then it'd be T(n) = T(n-1) + n.

---

why n-k=1?

Answer 1

Here 

n+module(n-1)

recursive call is module(n-1) only and n+module(n-1) is a constant addition

so recurrence realtion$= T(n)= T(n-1) + c$

                                           $ = T(n-2) +c +c= T(n-2) +2c$

                                          $ = T(n-k) + k \times c $

                                          here $n-k=1 \Rightarrow k=n-1$

                                         $ = T(n-n+1) + (n-1)*c$

                                         $=T(1) + (n-1)*c$

                                        $ =O(n)$

Comments

Sir , why is  T(n)= T(n-1) + n not true ??

---

$T(n) = T(n-1) + n$ means problem is reduced by $1$ in each step and we are doing $O(n)$ work in each step. But in the above problem we are only doing $O(1)$ work (simply adding $n$ to the value computed by module(n-1))

---

ok I got... thanks :)

---

well.. i wanted to ask that .. in    

module(n-1)+n      
 T(n-1)    for ,module(n-1)
  constant for ,  addition  

then for n ..?? what?

                               

---

@Shweta You are confusing between the return value of the function and the time complexity. Both are different and you should answer as per the question. Time complexity is like counting the cost of each operation and a + b, n + 1 etc. all are assumed to be of constant cost.

---

In what case will be the complexity be T(n-1) + n ?

Can you please give an example

---

The given recursion is counting the sum of first n natural numbers for the given n value.

so the time complexity will be O(n^2). But why is it O(n)?

---

Haseena try iteration for the same. Do you need a nested loop for sum of first n natural numbers? You will get it then.