AlgoScope

Big O

An upper bound on growth. O(n^2) means at most proportional to n^2 for large n, read off as what happens when n doubles.

Complexity analysis, analysis, beginner
n equals 2: counts 1, 1, 2, 2, 4, 4.124816321lg nnnlgnn^22^n110112021424
n equals 2: counts 1, 1, 2, 2, 4, 4.124816321lg nnnlgnn^22^n110112021424

Complexity in Numbers: Six classes as n doubles

Decision, step 3 of 8

n = 2. Doubling n added 1 to log n (0 to 1), doubled n, roughly doubled n log n (0 to 2), quadrupled n squared (1 to 4) and squared 2 to the n (2 to 4).

Cost

Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Complexity in Numbers covers these too, in the same run.