0

I have:

  • () = * log(!)
  • () = 3 * log(n)5n

I must show whether:

  • () = Ω(()) or/and
  • () = O(())

At first I tried to simplify (). This brings me to: () = 152 * log(n)

My next step would be to guess the factorial in (). For this I estimate an upper bound of . So now I can compare the two terms.

I know that: () ≤ O(())

* log() ≤ c * 2 * log(n)
2 * log(n) ≤ c * 2 * log(n)

So for c ≥ 1 → () = O(())

But how do I prove this for Ω? Or is my approach for O even right?

OmG
  • 18,337
  • 10
  • 57
  • 90
RoteZora
  • 35
  • 1
  • 5

2 Answers2

1

You will need Sterling's approximation. In short it states that ln(n!) = n * ln(n) - n + Θ(ln(n)) which directly leads to Θ(n * ln(n)) = Θ(ln(n!) See also this answer.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
1

To compare these functions you just need to take a log from them and note that log(n!) is in Theta(n log(n)). Hence, we have the following:

log(f(n)) = log(n log(n!)) = log(n) + log(log(n!)) => log(f(n)) is in `Theta(log(n))`

log(g(n)) = log(3n) + log(log(n)^(5n) = log(3n) + 5n log(log(n)) => log(g(n)) is in `Theta(n log(log(n)))`.

Therefore, as log(n), f(n), and g(n) are an increasing function, we can say that f(n) is in o(g(n)) (little-oh). Consequently, f(n) cannot be in Omega(g(n)), and definitely f(n) is in O(g(n)) (because Big-O(g(n)) is a subset of little-o(g(n))).

OmG
  • 18,337
  • 10
  • 57
  • 90
  • @RoteZora No, sorry, it means that `f(n)` is in `O(g(n))` and `f(n)` cannot be in `Theta(g(n))`. – OmG Jan 31 '22 at 16:31
  • @RoteZora as I showed, `f(n)` cannot be in `Theta(g(n))`! – OmG Jan 31 '22 at 16:35
  • But if `log(n!)` is `θ​(n log(n))` doesn't that equal to `n * log(n!)` being `θ​(n^2 log(n))`? Or is it wrong just do multiply the additionally n into θ?​ – RoteZora Jan 31 '22 at 16:38
  • Sorry I didn't see your first comment in time. – RoteZora Jan 31 '22 at 16:39