GATE Overflow | Algorithms | Test 1 | Question: 1

Question

For the following program fragment, the running time is given by

Procedure A(n) 
{
    if(n <= 2) 
        return 1; 
    else return A(log (n)); 
}

• A. $\Theta(\log \log n)$
• B. $\Theta(\log \sqrt n)$
• C. $\Theta(\log^* n)$
• D. $\Theta(\sqrt n)$

Comments

not able to how to approach please help me

---

can someone plz explain option C

what is * here??? 

Answer 1

$T(n) = T(\log n) + 1$

Solution to this recurrence is : no of times logrithmic function applied on $n$ in order to get base condition, which is nothing but $\log^* n$.

Complexity $=\Theta (\log ^*n)$

Comments

no it is very different u can check it by taking a simple example like take a number apply 2 times log and in second way take 1 time log and multiply it 2 times . u can see large differnce so

(logn)^2 not eql to log^2n

---

Applying Log 2 times will be Log(Log(x)) that is different from Log(x)* Log(x). but still Log²x = Log(x) * Log(x).

Its just same as Sin²(x)= Sin(x)*Sin(x)

---

sin^2x is not equal to sinx * sinx . just remember ur trignometry class if it is that much simple then why we apply cos2x formulae to calculate it just multipy two times and get result if u do this all trignometric identity gone wrong.

Answer 2

Let's take some values of n.

Clearly, the recurrence is  $T(n)=T(logn)+1$

I'll take it as $T(n)=T\left \lceil (logn) \right \rceil+1$ because $logn = O\left \lceil (logn) \right \rceil$

---

n = $1024$

$1024\rightarrow 10\rightarrow 4\rightarrow 2$

3 recursive calls.

So, for 1024, it is $O(loglogn)$

---

n = $2^{2048}$

$2^{2048}\rightarrow 2048\rightarrow 12\rightarrow 4\rightarrow 2$

4 recursive calls.

So, for $2^{2048}$ it is $O(logloglogn)$

---

n = $2^{2^{2^{2048}}}$

$2^{2^{2^{2048}}}\rightarrow $ $2^{2^{2048}}\rightarrow $ $2^{2048}\rightarrow 2048\rightarrow 12\rightarrow 4\rightarrow 2$

6 recursive calls.

So, for $2^{2^{2^{2048}}}$ it is $O(loglogloglogn)$

---

 

It is evident that number of logs is dependent upon how big the input value is. So, it would be Option C