Search⌘ K
AI Features
Home
Courses
Mastering Graph Algorithms

A Big-O Drill

Explore the fundamentals of Big-O notation and running-time analysis. This lesson teaches you to prove asymptotic upper bounds of functions and estimate running times of code segments using formal methods and practical examples.

We'll cover the following...

An easy warm up

Claim: nn is O(n)O(n).

To prove this, we want to find positive constants c′c' and n′n' for which

0≤n≤c′n for all n≥n′0 \leq n \leq c' n \qquad \text{ for all }n \geq n'

One way to approach a problem

Suppose we want to show that n2+2n+100n^2+2n+100 is O(n2)O(n^2).

Demonstration: To do this, we begin by showing an upper bound on each term of the form c×n2c \times n^2, for some constant cc.

For n≥1n \geq 1,

n2≤1n22n≤2n2100≤100n2\begin{align*} n^2 &\leq 1n^2\\ 2n &\leq 2 n^2\\ 100 &\leq 100 n^2 \end{align*} ...