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


Consider the following program

  if (n == 1)
     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
34,723 users