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

+15 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 (2.8k 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?

                               

+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)?
Answer:

Related questions

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
49,576 questions
54,182 answers
187,506 comments
71,143 users