retagged by
1,529 views
6 votes
6 votes

Consider the following piece of pseudo-code:

A(n){
    if(n==0) return 1;
    return A(√n) + B(n) + C(n) + D(n);
}
B(n){
    if (n==0) return n;
    return B(n-1);
}
C(n){
    return A (√n);
}
D(n){
    return n;
}

What is the time complexity in terms of Big $\Theta$ notation for the function call to procedure A?

  1. $\Theta(n)$
  2. $\Theta(n \log n)$
  3. $\Theta(n \log \log n)$
  4. $\Theta(n^2 \log n)$
retagged by

1 Answer

Best answer
15 votes
15 votes
Time complexity for $B(n), T_B(n) = T_B(n-1) + 1 \implies T_B(n) = \Theta(n)$

Time complexity for $D(n) = \Theta(1)$

So, time complexity for $A(n), T_A(n) = 2T_A\left(\sqrt n\right) + \Theta(n)$

For sake of simplicity rewriting $T_A$ as $S,$ we get

$S(n) = 2S(\sqrt n)+ \Theta(n)$

Substituting $n = 2^m$

$S(2^m) = 2S(2^{m/2}) + \Theta (2^m)$

Now taking $S(2^m) = R(m)$

$R(m) = 2R(m/2)+ \Theta(2^m)$

On this we can apply Master's theorem case 3, and we get $R(m) = \Theta (2^m)$

$\implies S(2^m) = \Theta(2^m)$

$\implies S(n) = \Theta(n)$
selected by
Answer: