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 ?
Best Answer
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$$