so the time complexity will be O(n^2). But why is it O(n)?

The Gateway to Computer Science Excellence

+5 votes

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)); }

- $O(n)$
- $O(\log n)$
- $O(n^2)$
- $O(n!)$

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

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.

+17 votes

Best answer

+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

well.. i wanted to ask that .. in

module(n-1)+nfor ,module(n-1)T(n-1)for , additionconstant

then for n ..?? what?

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,241 answers

198,009 comments

104,602 users