4,858 views
5 votes
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));
}
  1. $O(n)$
  2. $O(\log n)$
  3. $O(n^2)$
  4. $O(n!)$

1 Answer

Best answer
18 votes
18 votes

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

edited by
Answer:

Related questions

5 votes
5 votes
2 answers
1
go_editor asked Jul 1, 2016
6,465 views
Consider the following sorting algorithms.QuicksortHeapsortMergesortWhich of them perform in least time in the worst case?I and II onlyII and III onlyIII onlyI, II and II...
14 votes
14 votes
4 answers
2
ajit asked Sep 5, 2015
12,764 views
Suppose there are $11$ items in sorted order in an array. How many searches are required on the average, if binary search is employed and all searches are successful in f...
3 votes
3 votes
3 answers
3
go_editor asked Jul 1, 2016
3,247 views
Consider a 13 element hash table for which f(key)=key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would ...
3 votes
3 votes
1 answer
4
go_editor asked Jul 1, 2016
3,656 views
A computing architecture, which allows the user to use computers from multiple administrative domains to reach a common goal is called asGrid ComputingNeutral NetworksPar...