300 views

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)$

recategorized | 300 views
0
Function (B) has time complexity of O(n)

Function (D) has O(1)

Now, I Re-write the return statement of A as

return $A(\sqrt n)+O(n)+A(\sqrt n)+O(1)$

So, I form my recurrence for A as

$T(n)=2T(\sqrt n)+O(n)$

How Do I solve it?
+1
Read cormen book for this. Dont apply masters theorem all the time. it wont work here. In cormen book they have substituted it properly and solved.
0
Means, even my recurrence for A is incorrect?
0
Recurrence is fine. Just solve it by proper substitution. You will have your answer!!!
0

By solving your recurrence relation I got O ( n log n )

but it's not the correct answer :/

+1

@Ruturaj Mohanty I changed the options and also the notation to Big-Theta - otherwise there can be multiple answers.

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)$
by Veteran (431k points)
selected
+1
shouldn't it be $R(m)=2R(m/2)+\Theta(2^m)$ ?
0
Thanks. Corrected 👍
0

@Arjun

Sir could please give me reference for Masters theorem case 3 as u write in answer??

+3
That is in Cormen rt? Anyway when the functional part is exponential in the recurrence it should dominate the recursive part and Case 3 becomes trivial.
0

@Arjun sir,

you took S(2^m)=R(m) then s(2^(m/2)) should be R(m^1/2) but not R(m/2)

Logic: 2^m = x

m = log x

m/2 = (log x)/2

2^(m/2) = 2 ^ (log (x^1/2)) = x^1/2

Kindly correct me if i am wrong.

0
See I did not substitute $2^m = x.$ Actually I used a different function $S(x)$ and $R(x) = S(2^x)$ or $S(x) = R(\log_2 x)$
+1
Got it. Thanks sir🙂.