2k 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!)$
asked | 2k 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)?

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

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

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

+1
@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)?

1
2