The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
68 views

 

Consider the following program

foo(n)
{
  if (n == 1)
     P(n)
          else 
     Q() + foo(n-1); 
}


What is the time complexity for the given function, if the function ‘P’ and function ‘Q’ take O(n) and O(1) unit of time respectively.

  1.   O(n)
  2.   O(n2)
  3.   O(nlogn)
  4.   O(logn)

---------------------------------------------------------------------

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

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

T(n) =T(n-k) + c +c + c.......k times

put n-k =1

so,T(n) =O(n) +K*C       (T(1) =O(n))

hence,T(n) =O(n) +N-1*C

so,T(n) = O(n)

is this correct??

asked in Algorithms by Veteran (14.8k points) | 68 views

1 Answer

+1 vote
Best answer

Here for Base Case i.e., T(1) = O(n) ($\because$ it is given that P takes O(n) time)

In the statement Q() + foo(n-1) ===> Q() takes O(1) time.

So the recurrence relation is,

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

     = T(n-2) +1 +1

        ...

     =T(n-k) + k

    =O(n) + n-1

which gives O(n)

answered by Active (2.4k points)
selected by


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

29,017 questions
36,845 answers
91,385 comments
34,723 users