The Gateway to Computer Science Excellence
+4 votes
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)$
in Algorithms by Active (2.7k points)
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. 

1 Answer

+9 votes
Best answer
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 by
+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🙂.
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
198,209 comments
104,889 users