UGC NET CSE | Junet 2015 | Part 3 | Question: 33

Question

Which of the following is asymptotically smaller?

• A. lg(lg*n)
• B. lg*(lgn)
• C. lg(n!)
• D. lg*(n!)

Comments

here what is the different between  this ?  lg(n!) and  lg*(n!)

---

LG(n!) is LG (1*2*3*4*....*n) that is O(LG(n^n)) O(nlogn) LG*n is lglglg(any number of times)LG n

---

explanation:

https://math.stackexchange.com/questions/55720/which-is-asymptotically-larger-lg-lg-n-or-lg-lg-n

Answer 1

lg *n, (Inverse Ackermann function) is the number of times we can take log repeatedly until we get 1. This function can almost be considered constant for all practical purposes.

There shouldn't be any confusion regarding options C and D as n! is asymptotically larger than lg n.

A) lg (lg * n)
B) lg * (lg n)

As per the definition of lg *, we can write B as

lg * (lg n) = lg * n - 1.

So, A is asymptotically lower than B.

A < B < D < C.

Comments

Sir I have just one confusion in this as u said that for lg *n, This function can almost be considered constant for all practical purposes. so then considering 

A) lg (lg * n)
B) lg * (lg n)

A would evaluate to calculating lg(constant) while B would evaluate to repeatedly applying log on a log value so it would be then much smaller than the value computed in part A , so then B must be asymptotically smaller than A ,plz crect me where I am making mistake .

---

If you go intuitive way, lg of an almost constant must be smaller than an almost constant rt?