GATE Overflow Test Series | Mixed Subjects | Test 2 | Question: 5

Question

For the below function, arr is pointing to an array of $len$ elements. The complexity of the function is

void func(int * arr, int len)
 {
     if(len == 0)
         return;
     printf("%d ", arr[0]);
     func(arr+1, len-1);
 }

• A. $O(n)$
• B. $\Theta( n^2)$
• C. $O(1)$
• D. $\Theta(n \log n)$

Answer 1

We can write the recurrence relation $,T(n) = \left\{\begin{matrix} T(n-1) + C&;n\geq 1 \\  C&;n = 0 \end{matrix}\right.$

$T(n) = T(n-1) + C\quad \rightarrow (1)$

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

$T(n-2) = T(n-3) + C$

$T(n-3) = T(n-4) + C$

$T(n-4) = T(n-5) + C$

$T(n-5) = T(n-6) + C$

Put all these values, in the equation $(1),$ we get

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

$T(n) = T(n-2) + C + C$

$T(n) = T(n-3) + C + C + C$

$T(n) = T(n-4) + C + C + C + C$

$T(n) = T(n-5) + C + C + C + C + C$

$\;\;\;\;\;\;\;\vdots \;\;\;\;\;\;\;\vdots \;\;\;\;\;\;\;\vdots$

For $k^{\text{th}}$ iteration.

$T(n) = T(n-k) + kC$

$n-k = 0,T(0) = C$

$\implies k = n$

$T(n) = C + nC = Cn = O(n).$

So, the correct answer is $(A).$