Member Avatar for SeePlusPlus2

What exactly does it mean when an algorithm has a run time of Omega(nlgn) or Theta(n^2), etc. From what I can tell, Big O is used to show the worst case(?) while Omega is best(?) and Theta is either(in between O and Omega?. I'm having a hard time understanding this topic. The reason I ask is because the book would ask questions like :

"Show that the running time of QUICKSORT is Theta(n^2) when the array A contains distinct elements and is sorted in decreasing order."

or

"What is the running time of QUICKSORT when all eleents of array A have the same value?"

How do you solve problems like these?

Edited by SeePlusPlus2
  • 2 Contributors
  • 3 Replies
  • 231 Views
  • 11 Hours Discussion Span
  • Latest Post Latest Post by sepp2k
Member Avatar for sepp2k

The distinction between O, Theta and Omega isn't about best- versus worst-case. You can use any of these notations to analyze any case you want. That is, the statements "QuickSort's worst case is in Theta(n^2)" and "QuickSort's best case is in Theta(n log n)" are both valid usages of Theta.

Instead the distinction is that O specifies an upper bound, Omega a lower bound and Theta both. What this means is that "Foo is in O(n^2)" means that Foo is quadratic or less (that is when something is linear, it's also in O(n^2) because linear is less than quadratic). Similarly Omega(n^2) means quadratic or more (that is something qubic or even exponential will also be in Omega(n^2)). Theta(n^2) means it's exactly quadratic. That is when something is quadratic, it's in Theta(n^2), but something that's linear, cubic or exponential is not. Something is in Theta(f(n)) if it is both in O(f(n)) and Omega(f(n)).

Member Avatar for SeePlusPlus2

How can you tell what an algorithm's run time notation is by looking at it?

Edited by SeePlusPlus2
Member Avatar for sepp2k

Do you mean "how to tell what an algorithm's run time is" or "how to tell which notation to use (i.e. O or Theta or Omega)"? If you mean the latter: You should use the notation that the assignment asks for. when in doubt, use Theta as its the most specific.

If you mean the former: The basic approach is to understand exactly what the algorithm does and then ask yourself how many steps it will take for a given n. Of course that's easier said than done. Plenty of tutorials have been written about this.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.