Algo doubt

Question

iterated logarithmic function is defined as

$\log^*n = \begin{cases} 0  &\text{if }\quad n\leq 0 \\1 +\log^*(\log n) &\text{if } \quad n >1\end{cases}$

Which of the following is true?

• A. $\log^*n = O(\log(\log n ))$
• B. $(\log^*n)!= O(\log n)$
• C. $\log^* n = \Theta(\log n)$
• D. $(\log^*n)^n= O((\log n)!)$

Comments

already discused by arjun sir.

---

@Anirudh plz post the link ...

Answer 1

This is better done by taking larger values of  'n' ..

Let  $n  =  2^{65536}$

So evaluating the iterated logarithmic function as defined in the question for $n  =  2^{65536,$  we get :

$\log ^* (2^{65535})   =  1 + \log ^* (65536)$  

$\qquad =  1 + 1 + \log ^* (16)$

$\qquad =  1 + 1 + 1 + \log ^* (4)$

$\qquad =  1 + 1 + 1 + 1 + \log ^* (2)$

$\qquad =  1 + 1 + 1 + 1 + 1 + \log ^* (1)$

$\qquad  =  5$

Hence  $\log ^* (2^{65536})    =   5$

Now $\log(\log(2^{65536})     =   16$

And this distance between log * (n) and log(logn) will further increase with increase of 'n'..

Hence  log * n   =   O(log(logn))  is true

Now (log * n)!    for the taken value of 'n'   =   5!  =  120

       $ \log n     =    \log 2^{65536}      =    65536$

And this distance will further increase with higher value of 'n'

Hence    (log * n)!  =   O(logn) should be true as well.

Option C is clearly false as $\log^* n = o(\log n)$ as shown for option A.

Now

$(\log ^* n)^n      =   5^{2^{65536}}$

$(\log n)!         =   (65536)!$

Now clearly  the first one in this case is greater than the second one. One can verify this by comparing $5^{2^n}  = (n!)$ ..So taking log both sides , we get :  $2^n$  in LHS and  $\log(n!) = n\log n$ in RHS so LHS  > RHS .

Hence $(\log^* n)^n   =   \omega ((\log n)!)$ and not $O((\log n)!)$

Hence A,B) should be the correct option .

Comments

Thanku...:)

---

i am not getting this

log * (2⁶⁵⁵³⁵)   =  1 + log * (65536)  ??

Answer 2

For this we have to consider a large number .Let us take $n = 2^{1000}$ for our calculation.

So using the above definition ,

A) $\log^*(2^{1000}) = 4$   and   $\log(\log 2^{1000}) = 9$

With higher numbers this difference will further increase.

So , $\log^* n = O(\log(\log n))$

So statement A should be true.

B) $(\log^*2^{1000}) !  =   4!   = 24$   and  $\log 2^{1000} =  1000$

So LHS is already much smaller than RHS.

Hence statement B is also true.

Now let us come to the trickiest claim

C) False, as option A is true

D)  $(\log6 * 2^{1000})2^{1000}   =     4^{2^1000}$        and

RHS  =   $((\log2^{1000} )!)   =   (1000)!$

 Now here let $x = 1000$  and let $a = 4$..Hence LHS can be rewritten as:

  $a^{2^x}$   and   RHS can be written as $x !$

 Now to compare these , applying logarithm both sides , we have :

 $2^x \log a$   and RHS is $\log(x)!$ which can be approximated as $x\log x$ [By Stirling's approximation]

 So obviously,  $2^x \log a > x\log x$

    (or)            $2^x\log a = \omega(x\log x)$

    (or)            LHS    =  $\omega$(RHS)

Hence the claim D) is false.

Hence , in the given question , statements A) and B) only should be true.

Comments

With higher numbers this difference will further increase.

This is the most important thing. But you did not use this for second case and hence the proof is not complete for Case 2.

For case 3 we can also do as follows:

LHS is growing faster than an exponential function. (Consider base as 2). RHS is $n \log n$ after Stirling's approximation. Hence, false.

---

I agree Arjun sir.. I just took an example.. We can take even larger number.

---

I mean however large example we take, we should always take 2 example values and consider the relative change.