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

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.