The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
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 in Algorithms by Veteran (103k points) | 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)?

1 Answer

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

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

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


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

40,808 questions
47,492 answers
145,716 comments
62,249 users