Tag Info

Is Big-Theta a more accurate description of worst case run time than Big-O?

You answer yourself by saying that $\Theta$ is the conjunction of $O$ and $\Omega$. So yes of course, $\Theta$ is more informative than $O$ alone. Make sure anyway that you don't confuse the ...
• 5,147

Is Big-Theta a more accurate description of worst case run time than Big-O?

O(f(n)) is also used when there is no simple function that your runtime is close to. For example: Find the smallest prime factor of n by trial division, finishing when a factor is found: There are O(n^...
• 25.9k
Accepted

Is Big-Theta a more accurate description of worst case run time than Big-O?

Yes. Your understanding is correct on all points!
• 144k
Does $L = \{a^n \ | \ n \geq 1, \ n \ \text{ is even or a square number}\}$ have infinite equivalence classes?
Change the description to "n is even or an odd square". For every r, let $k = 4r^2$. $a^k a^j$ is in the language if j is even, or if j is odd and k+j is a square. The smallest odd j is \$(4r+...