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
  • 245 Views
  • 11 Hours Discussion Span
  • Latest Post Latest Post by sepp2k

Dani AI

Generated

A short, hands‑on way to read an algorithm and apply the notations mentioned by (building on ’s conceptual point) is: 1) pick a simple cost measure (comparisons or swaps), 2) find the structure that controls how that cost grows (loops or recursion), 3) set up a count or a recurrence, and 4) solve it (sum, recursion tree, or Master theorem). The book exercises are best answered by that mechanical approach rather than by memorizing labels.

Apply that to the two QuickSort cases in the post. With the usual single‑pivot partition (Lomuto/CLRS style) and pivot taken deterministically (first or last):

Each partition step does Theta(n) work and leaves subproblems of sizes (0,n-1).
Recurrence: T(n) = T(n-1) + Theta(n)
Sum: Theta(1+2+...+n) = Theta(n^2)

So QuickSort is Theta(n^2) for the strictly decreasing array example. For an array where all keys are equal, the same single‑pivot partition also places the pivot at one end each time, producing the identical recurrence and Theta(n^2) cost for that implementation.

A clarifying note: a different partition strategy changes the result. Three‑way (Dutch‑flag) partitioning groups <,=,> around the pivot and finishes in one linear pass when all keys are equal, giving Theta(n) for that input. Randomized pivot choice changes worst‑case probability (expected time becomes Theta(n log n)), but does not remove the degenerate behavior of a poor partition scheme on many duplicates.

Practical checklist: when inspecting code, (a) count dominant operations, (b) turn recursion into a recurrence and solve it, (c) watch how equal keys and pivot selection affect subproblem sizes, and (d) use three‑way partitioning or random pivots when duplicates are common. Use Theta when a tight (both upper and lower) bound is provable for the specific input condition named in the exercise.

Recommended Answers

All 3 Replies

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.