Big O Notation Exercise

Question

I'm having a small problem. I'm very new in this section so please bear with me. I understand Big O meaning what everything signifies like the $O(n), O(n^2), O(x^n), O(\log n)$ and $O(1)$.

I also learn the very basic of $\Omega$ and $\Theta$. The problem that I have is I'm being as to represent this as a theta: $T(n) = 2n+\log^2n$

I am not sure what the answer is i just assumed it was $\Theta(n)$ because we're talking about worst case algorithm. Am I correct ?

@O.B.D.A., that question doesn't mention theta. – Gerry Myerson Mar 08 '14 at 22:59 — Gerry Myerson, Mar 08 '14 at 22:59

score 1 · Accepted Answer · answered Mar 08 '14 at 23:03

1

Yes, $2n+\log^2n$ is $\Theta(n)$, but not because you are talking about algorithms, worst case or otherwise. $2n+\log^2n$ is $\Theta(n)$ because there are constants $k_1$ and $k_2$ such that, for large $n$, $$k_1n\le2n+\log^2n\le k_2n$$

answered Mar 08 '14 at 23:03

Gerry Myerson

179,216

Thank you for answering appreciate the help! :) – Yann Bohbot Mar 08 '14 at 23:18
Can you tell me what values would the constants have? Thanks :) – GniruT Oct 23 '15 at 18:48
1

@Gniru, you can take $k_1$ to be any number not exceeding 2, and for $n$ large enough you can take $k_2$ to be any number exceeding 2. – Gerry Myerson Oct 23 '15 at 23:29

Big O Notation Exercise

1 Answers1