开发者

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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜