The Gateway to Computer Science Excellence
+5 votes
2.3k views

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));
}
  1. $O(n)$
  2. $O(\log n)$
  3. $O(n^2)$
  4. $O(n!)$
in Algorithms by Veteran (105k points) | 2.3k views
0
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)?
+1

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.

1 Answer

+17 votes
Best answer

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)$

by Active (2.8k points)
edited by
+1
Sir , why is  T(n)= T(n-1) + n not true ??
+3

$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))

0
ok I got... thanks :)
0

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?

                               

+2
@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.
0
In what case will be the complexity be T(n-1) + n ?

Can you please give an example
+1
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)?
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,241 answers
198,009 comments
104,602 users