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

}

This question was previously asked in

ISRO Scientist CS 2014 Official Paper

- O(n)
- O(log n)
- O(n
^{2}) - O(n!)

Option 1 : O(n)

Free

ISRO Scientist CS 2020 Official Paper

778

80 Questions
240 Marks
90 Mins

** Answer**: Option 1

** Explanation**:

f(n) = n + module(n-1); // since **return (n + module(n-1));**

Here recurrence relation will be

T(n) = T(n-1) + c

≡ T(n-2) + c + c

≡ T(n-3) + 3c

≡ T(n-k) + kc

when n-k = 1 ; k = n-1 and T(1) = 1

≡ T(1) + (n-1)c

≡ (n-1)c

≡ O(n)

Hence Option 1 is correct answer.

Here some of you might have cam up with recurrence relation T(n) = T(n-1) + n, which is incorrect because in function n is just a variable it will have a constant value which will get added to call return value and In recurrence variable n indicate cost.

India’s **#1 Learning** Platform

Start Complete Exam Preparation

Daily Live MasterClasses

Practice Question Bank

Mock Tests & Quizzes

Trusted by 2,29,04,206+ Students

Testbook Edu Solutions Pvt. Ltd.

1st & 2nd Floor, Zion Building,

Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

[email protected]
Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

Toll Free:1800 833 0800

Office Hours: 10 AM to 7 PM (all 7 days)