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.
- O(n)
- O(n2)
- O(nlogn)
- 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??