Skip to content
doubtly

1 answer

Big-O gives an upper bound, Omega (Ω) a lower bound, and Theta (Θ) a tight bound on how an algorithm's running time grows with input size \(n\).

1. Big-O (upper bound). \(f(n) = O(g(n))\) if there are constants \(c > 0\) and \(n_0\) such that

\[0 \le f(n) \le c\,g(n)\ \text{ for all } n \ge n_0.\]

Diagram: after \(n_0\), the curve of \(f(n)\) always stays below the curve \(c\,g(n)\). Used for worst case. Example: \(3n + 2 = O(n)\) with \(c = 4, n_0 = 2\).

2. Omega (lower bound). \(f(n) = \Omega(g(n))\) if

\[f(n) \ge c\,g(n) \ge 0\ \text{ for all } n \ge n_0.\]

Diagram: after \(n_0\), \(f(n)\) stays above \(c\,g(n)\). Example: \(3n + 2 = \Omega(n)\) with \(c = 3\).

3. Theta (tight bound). \(f(n) = \Theta(g(n))\) if

\[c_1 g(n) \le f(n) \le c_2 g(n)\ \text{ for } n \ge n_0.\]

Diagram: after \(n_0\), \(f(n)\) lies between the two curves \(c_1 g(n)\) and \(c_2 g(n)\), like a sandwich. Example: \(3n + 2 = \Theta(n)\) with \(c_1 = 3, c_2 = 4\).

How time complexity is analysed and measured.

  1. Choose the input size \(n\) (number of elements, nodes, digits, etc.).
  2. Identify the basic operation (comparison, addition, swap) that runs most often.
  3. Count how many times it runs as a function of \(n\): a single loop gives about \(n\); two nested loops give about \(n^2\); halving the input each step gives \(\log n\); for recursive algorithms, write a recurrence such as \(T(n) = 2T(n/2) + n\) and solve it (substitution, recursion tree or Master theorem).
  4. Keep only the highest-order term and drop constants: \(5n^2 + 3n + 7 = O(n^2)\).
  5. State best, average and worst case separately where they differ (e.g. linear search: best \(O(1)\), worst \(O(n)\)).

Common growth order: \(1 < \log n < n < n\log n < n^2 < n^3 < 2^n < n!\).

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.