0

I have been trying to understand weather I can reduce this to more simple possible terms? : $$\Theta(n^3)+\Theta(n^2 \log^2(n))$$

I know that $O(\log^2(n))=O(n^a)$ for $a > 0$. But I'm not sure if that true with theta notation.

mathreadler
  • 25,824
Anirudh Gangwal
  • 133

1 Answers1

0

The theta notation means a strict upper bound, which means that no function more closely bounds the complexity than the function inside the parentheses. For instance, you could say Heapsort is bounded by $O(n\log n)$, $O(n^2)$, or $O(n^n)$ steps, but you could only say that it is bounded by $\Theta(n\log n)$ steps. By the same token, Heapsort is bounded by $\Omega(n)$, $\Omega(n\log(n))$, and $\Omega(1)$. Now, to answer your specific question, since this is asymptomatic, you can add them together and ignore the lower order terms.

AlgorithmsX
  • 4,560
  • This is the worst case of an algorithm. So can I add the two up? Which one is the lower order term here? – Anirudh Gangwal May 07 '17 at 23:39
  • Here's a really good question with some useful information. Basically, $\Theta(f(n))\implies O(f(n))=\Omega(f(n))$. Both the upper bound and the lower bound are the same. http://stackoverflow.com/questions/10376740/what-exactly-does-big-Ө-notation-represent – AlgorithmsX May 07 '17 at 23:44
  • Also, the lower order term is the second one by the reasoning you gave in your question. – AlgorithmsX May 07 '17 at 23:46
  • Oh, so since I have theta(n^3), the whole term becomes theta(n^3). Say I didn't have the theta(n^3) term, then could I write the just the right term as theta(n^3)? If I understand correctly, I can't in that case. – Anirudh Gangwal May 07 '17 at 23:48
  • 1
    First statement is correct. The second statement is wrong because you would still have $\Omega(n^2\log^2 n)$ as the greatest lower bound, which does not equal $O(n^3)$. Theta notation means that the upper bounds and the lower bounds are equal to within a constant. – AlgorithmsX May 07 '17 at 23:52