Big O, Omega and Theta Exercises

Question

i have a few exercises to do but i need someone to correct me if they can. I am very new to the Big O notation so please forgive me for being too basic.

I need to represent everything under Θ.

T(n) = 10n + 2^(2*log n) --> Answer= Θ(n)

T(n) = n^2.5 + n^log 4 --> Answer= Θ(n^2.5)

T(n) = n log n + n^1/2 --> Answer = Θ(log n)

Am I right? or am i missing something?

score 1 · Answer 1 · answered Mar 09 '14 at 00:03

1

In the third, both $n\ln n $ and $n^{1/2}$ are much bigger than $\ln n$. But your other two are correct.

answered Mar 09 '14 at 00:03

davidlowryduda

91,687

Thanks so what's the answer for the third one? – Yann Bohbot Mar 09 '14 at 00:04
which of the two terms is bigger? – GEdgar Mar 09 '14 at 00:20

score 0 · Answer 2 · answered Mar 09 '14 at 00:48

0

For the third one, to be explicit, it is $\Theta(n \ln n)$, since that is larger that $n^{1/2}$.

answered Mar 09 '14 at 00:48

marty cohen

107,799

Big O, Omega and Theta Exercises

2 Answers2