CODEWITHSUNDEEP
algorithmasymptotic-complexity
WSS
WSS

Reputation: 513

What is the asymptotic relation between functions

I want to know the reason of following given relations:

  1. n < (log n)^log n
  2. log log n = O(root(log n))
  3. (log n) != omega(log(n!))
  4. log(log*n) < log*(log n)

base of all log is 2. Obviously I know the answers but I do not know how to find them.I could also see one can not find these just by putting values of n all the time. As for 1st relation it does not hold for n=2. What is the effect of applying above function to large value of n? Can anyone come with universal solution (or guide me a way) so that I can find relation on applying different combination of above (or extra function not given) functions on n. For example, log*log(root(log(n!))) with loglog*(log(root(n!)))

Upvotes: 0

Views: 3708

Answers (1)

Andrew Tomazos
Andrew Tomazos

Reputation: 68698

Roughly speaking, asymptotic means as approaches infinity (as the function approachs its asymptote).

So for a rough estimate, use really large n.

For a more precise definition and discussion see Asymptotic Analysis, or any intro to computer science text.

Upvotes: 2

Related Questions