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(n2) is true
n·ln(n) ≤ c·n2 for c = 1, ∀n ≥ 0
n·ln(n) ∈ Ω(n2) is false
n·ln(n) ≱ n2 hence ln(n) < c·*n* for c = 1, ∀n ≥ 0
n·ln(n) ∈ O(n·(log(n))2) is true
n·(log(n))2 = n·(ln(n)/ln(2))2 = n·(ln(n))2/(ln(2))2 and n·ln(n) ≤ c·n·(ln(n))2/(ln(2))2 for c = (ln(2))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
精彩评论