The Gateway to Computer Science Excellence
+4 votes

Consider the following piece of pseudo-code:

    if(n==0) return 1;
    return A(√n) + B(n) + C(n) + D(n);
    if (n==0) return n;
    return B(n-1);
    return A (√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
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?
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.
Means, even my recurrence for A is incorrect?
Recurrence is fine. Just solve it by proper substitution. You will have your answer!!!

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

but it's not the correct answer :/


@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
shouldn't it be $R(m)=2R(m/2)+\Theta(2^m)$ ?
Thanks. Corrected 👍


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

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.

@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.


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)$
Got it. Thanks sir🙂.

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
104,889 users