What is the time complexity for the following C module? Assume that $n>0$.
int module(int n)
if (n == 1)
return (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$
$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))
well.. i wanted to ask that .. in
T(n-1) for ,module(n-1)
constant for , addition
then for n ..?? what?
First of all, congratulations!
Please elucidate this really important...