I have 2 doubts:-
1) Is (log* n)^n = O((logn)!) ?
2) Which is bigger, log(log* n) or log*(logn) ?
Asked
Active
Viewed 608 times
-2
templatetypedef
- 362,284
- 104
- 897
- 1,065
Zephyr
- 1,521
- 3
- 22
- 42
-
It is known as iterated logarithm ! You can check here :- https://en.wikipedia.org/wiki/Iterated_logarithm – Zephyr Aug 16 '17 at 10:03
-
-.- it's log star and not a multiplication. I am sorry :) It was hard to notice. – Tony Tannous Aug 16 '17 at 10:05
-
I know it's hard to notice. That's why I mentioned it in the title of the question. Can you help me with this question ? – Zephyr Aug 16 '17 at 10:06
-
I am not sure why I am receiving down votes. Did I ask something wrong ? – Zephyr Aug 16 '17 at 10:21
-
2You showed 0 efforts. (I didn't Down voted you). – Tony Tannous Aug 16 '17 at 10:22
1 Answers
5
For 2), you have log*(log n) = log*(n)-1. Then let m = log*(n). You have m-1 > log(m) for sufficiently large m.
Hint:
For 1), let m = log*(n). Then the LHS is m^n, and the RHS is the factorial of the logarithm of an exponential tower of height m, i.e. the factorial of an exponential tower of height m-1.
Even disregarding the factorial, an exponential tower should grow much faster than a power.
-
2
-
-
-
-
Just let me know if I am correct . In 1st case, we can consider log*n as approximately a constant (let it be k) . Now k^n = O(n!). So for very large n, k^n = O((logn)!). Hence (log *n)^n = O((log n)!). Am I correct? – Zephyr Aug 17 '17 at 08:21
-