Geek asks and answers

Is log (n) = Ω (n)?

I believe not. The definition is that:

log(n) >= c*n for some n = x, and all n > x

The reason I don't think the growth rate is c * n = c. Growth rate log (n) = 1 / n. Thus, when n -> infinity, the growth rate n approaches 0, and c - the growth rate c * n, is constant. Given that ultimately log (n) will eventually grow slower than any n * c, where c> 0, n * c will go over log (n).

So a few questions.

  • Can c> 0 be considered from the definition of a large omega?
  • Is my intuition above correct?
  • I contradicted my proof above. Since for very small c, log (n) = cn is very early, my assumption above means that they will intersect again, which means that log (n) = cn has more than one solution, which seems wrong.

I am very confused and appreciate the help!

+3
source share
2 answers

1- c cannot be 0 or negative, so you can assume that.

2. Growth is log(n)lower than growth nfor each n > 1, for example. Since Ω (n) is a set of functions that “grow more” than a function f(n) = n, log (n) is not Ω (n). But you could say n = Ω (log (n)), although that would not be an asymptotic dense estimate.

3- , , n0. - n0 , . (log (n) = Ω (n)) , n >= n0. , log (n) n .

+6

, .

  • log(n) O(n)

[: , fn, n]

  • fn n - Ω(log(n))

    [: - fn, log(n)]

, . log(n)=cn .

+1
source

More articles:


All Articles