Big O Bounds: Definitions, Growth Rules, and Related Notation

All flashcards

What is Big O notation?

A notation expressing an upper bound on a function’s growth relative to a comparison function, often used to classify algorithm resource use.

What does the comparison function represent?

It gives the growth scale used to bound the function being studied, such as $n$, $n^2$, or $2^n$.

What is the implied constant?

The positive constant $M$ for which $|f(x)| \le Mg(x)$ on the stated domain. Its exact value is commonly left unspecified.

Why does the domain matter in Big O?

The inequality must hold on the stated domain. A bound may be valid for sufficiently large inputs but fail for some smaller inputs.

Does $f=O(g)$ mean $f$ equals $g$?

No. The equals sign is conventional shorthand for a bound; it does not state that the functions have equal values.

Quiz questions

1. What does a statement that an algorithm's running time is $O(g(n))$ establish?Answer: Its running time is bounded above by a constant multiple of $g(n)$ over the stated range.
2. For $f(n)=6n^4-2n^3+5$ with $n\ge1$, what is its standard large-input Big O bound?Answer: $O(n^4)$
3. What does $f(x)=O(g(x))$ as $x\to a$ mean when $a$ is finite?Answer: The bound holds in a neighborhood of $a$, subject to the functions’ domains.
4. Why is $x\sin y=O(x)$ for $x\ge1$ and every real $y$ a uniform bound?Answer: One constant works for every allowed $x$ and $y$ because $|\sin y|\le1$.
5. For positive functions, what does $f=\Theta(g)$ mean?Answer: Each function is bounded above by a constant multiple of the other.