Member Avatar for arh

Hi guys. Gotta a CS exam coming up this sunday and I want to clarify the difference between bigO and theta notation. I know that bigO is the upperbound and it has a constant after which all running time will be below. I know that theta has an upper and lower bound for this running time, but I'm still a bit confused. Here are some questions:

1) Do big-oh and theta both represent the worstcase for the running time?
2) How do I know when to use theta? I know it is better to use but how do I know when I can use it? Could someone give a simple example of when to use theta?


thanks in advanced,

arh

  • 3 Contributors
  • 3 Replies
  • 290 Views
  • 5 Days Discussion Span
  • Latest Post Latest Post by Eko

Dani AI

Generated

A short, practical primer tied to the posts by , and .

Big-O is an asymptotic upper bound: writing f(n) = O(g(n)) means there exist constants c > 0 and n0 such that f(n) ≤ c·g(n) for all n ≥ n0. Θ (Theta) is a tight (both upper and lower) bound: f(n) = Θ(g(n)) means there exist c1,c2 > 0 and n0 with c1·g(n) ≤ f(n) ≤ c2·g(n) for all n ≥ n0. These are the standard formal definitions and the usual simplification rules (drop constants and lower-order terms). Big O notation (Wikipedia), Theta (NIST DADS). (en.wikipedia.org)

Answer to Q1: they do not intrinsically mean “worst‑case.” The notation just describes an asymptotic bound for whatever case is being measured (best, average, or worst) — the author must state which case. was correct: specify the case when giving a complexity. See standard course notes on asymptotic concepts for the same point. Asymptotic concepts (course notes). (ics311.github.io)

Answer to Q2: use Θ only when a tight bound can be proved (i.e., show both O and Ω). Example: f(n) = 3n^2 + 5n + 2. For n ≥ 1,

3*n^2  ≤  3*n^2 + 5*n + 2  ≤  10*n^2

so f(n) = Θ(n^2) (take c1 = 3, c2 = 10, n0 = 1). In practice, show f(n) = O(g(n)) and f(n) = Ω(g(n)) to conclude Θ(g(n)). Θ definition (GeeksforGeeks) and the Big‑O rules above are a good reference. (geeksforgeeks.org)

Practical tip: state the case (best/average/worst) whenever using O, Ω or Θ. For example, randomized quicksort runs in Θ(n log n) on average but can be Θ(n^2) in the worst pivot choices — so writing “quicksort is Θ(n log n)” without saying “average case” is misleading. ’s pointer to course lectures is useful for worked examples. Quicksort complexities (GeeksforGeeks). (geeksforgeeks.org)

Recommended Answers

All 3 Replies

Member Avatar for Narue

>1) Do big-oh and theta both represent the worstcase for the running time?
They represent whatever case you're analyzing.

>2) How do I know when to use theta?
Theta is when you can achieve it. It's a much stronger claim than Big O because it's a tighter bound.

Member Avatar for arh

Thanks for the reply. I was able to figure it out by reading some other stuff online.

Member Avatar for Eko

For those who want to understand the asymptotic notation, try this link:

It's a very good site with video lectures from m.i.t.(the asymptotic notation is in the second lecture)

Good luck

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.