Big-O Notation

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

f(n) = O(g(n)) means f(n) grows no faster than g(n).

◇Details / Theory

Asymptotic Upper Bound.

f(n) = O(g(n)) means f(n) grows no faster than g(n). It represents the Worst-case running time of the algorithm. Formal Definition: O(g(n)) = { f(n) | ∃ c > 0, n₀ > 0 such that 0 ≤ f(n) ≤ c⋅g(n) for all n ≥ n₀ } (Handout 03, Page 3)
Example: 6n³ + 2n² + 3n + 8 is O(n³). Also O(n⁴), O(2ⁿ), etc. We usually seek the tightest un-nested loops are a fundamental control structure where one loop is contained within another. They are particularly important in frequency counting because they often represent the most computationally expensive parts of algorithms.
Is the function also $O(n^4)$? How about $O(n^6)$?
Yes, since the function grows no faster than $n^4$ and $n^6$
The function is $O(n^c),c≥3$

◇Complexity

◇Common Pitfalls

Thinking $O(n)$ always means exactly $n$ operations — it means at most proportional to $n$. Forgetting that Big-O gives an upper bound, not a tight bound — $O(n^4)$ is technically correct for a $\Theta(n)$ algorithm.

◇Summary

TL;DR — Big-O ($O$) gives an asymptotic upper bound: $f(n) = O(g(n))$ means $f(n)$ grows no faster than $g(n)$. It represents the worst-case growth rate.

◇Links

Related: Source / Reference:

◇References & Navigation

• Previous Topic: ◇Best-Case Analysis
• Next Topic: ◇Big-Omega Notation
• Related Notes: ◇Big-Omega Notation, ◇Big-Theta Notation