Time complexity and Big-O notation specific question

A question in one of my past exams is a multi-choice question:

Choose the FALSE statement: 7(log n) + 5n + n(log log n) + 3n(ln n) is

A. O(n^2)
B. Ω(n^2)
C. O(n log^2 n)
D. Ω(n)
E. Θ(n log n)

First I concluded that the running time of the algorithm had to be Θ(n log n), which ruled out option E. I then concluded that Option B, Ω(n^2), ws false, because I knew that Θ(n log n) was smaller than Θ(n^2), therefore Ω(n^2) could not be true. So I thought B would be the answer.

But I also realised that C couldn't be true either, since Θ(n log n) is a larger running time than Θ(n log^2 n). But it couldn't p开发者_运维问答ossibly be 2 of the answers correct.

So which is correct: is it B? or is it C? or neither? I'm so confused. :S

---

the false statement is omega(n^2).
it is exactly theta(nlogn) (since 3n(ln n)) is the "highest", and it is theta(nlogn).
omega(n^2) says it is not better then n^2 complexity, which is false in here.

addition: in your example the following is true:
7(log n) < 5n < n(log log n) < 3n(ln n)
7logn = theta(logn), 5n = theta(n), n(loglogn) = theta (nloglog(n)), 3nln(n) = theta(nlogn)
which as said, (nlogn) is the highest, thus:
7(log n) + 5n + n(log log n) + 3n(ln n) = theta(nlogn)
and all are o(n^2) (small o here on purpose), so Omega(n^2) is the false statement.

EDIT: clarifying and adding what I've wrote in comments:
option C is True because O(nlogn) < O(nlog^2(n)). mathematically:
nlog^2(n) = n*log(n)*log(n) > n*log(n) for every n>2.
example: for n=1,000,000: nlogn = 1,000,000*20 = 20,000,000
while n*log^2(n) = 1,000,000*20*20=400,000,000.

---

Assuming that log is the base 2 logarithm and ln is the natural logarithm, the following statement is true:

Θ(log(n))  <  Θ(n·log(log(n)))  <  Θ(n)  <  Θ(n·ln(n))

So the overall complexity is Θ(n·ln(n)).

Now let’s check the statements:

• n·ln(n) ∈ O(n²) is true

  n·ln(n) ≤ c·‍n² for c = 1, ‍∀n ≥ 0

• n·ln(n) ∈ Ω(n²) is false

  n·ln(n) ≱ n² hence ln(n) < c·*n* for c = 1, ‍∀n ≥ 0

• n·ln(n) ∈ O(n·(log(n))²) is true

  n·(log(n))² = n·(ln(n)/ln(2))² = n·(ln(n))²/(ln(2))² and n·ln(n) ≤ c·‍n·(ln(n))²/(ln(2))² for c = (ln(2))², ∀n ≥ e

• n·ln(n) ∈ Ω(n) is true

  n·ln(n) ≥ c·‍n for c = 1, ∀n ≥ 0

• n·ln(n) ∈ Θ(n·log(n)) is true

  n·log(n) = n·ln(n)/ln(2) and n·ln(n) = c·‍n·ln(n)/ln(2) for c = ln(2), ∀n ≥ 0