New answers tagged

0 votes

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
8 votes

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
9 votes
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
0 votes
Accepted

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+...
  • 25.9k

Top 50 recent answers are included