find the total time

Question

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(n²)
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??

Answer 1

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)