Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 18m 45s17 days 22 hours 18 minutes 45 seconds.

Algorithms - Foundations · 4:15

Big-O, Amortized Analysis and Logarithms

How to count work precisely: Big-O keeps only the shape of the cost, loops add or multiply, and hidden loops like s = s + c turn one loop into two. We halve a million candidates down to one in 20 steps, push 17 numbers into a vector and count 31 moves to see amortized O(1), measure the rare slow push that reserve() removes, and find the n log n hiding in the harmonic sum.

You will learn

Simplify a cost to its Big-O class and distinguish O, Omega and Theta
Count the work of sequential, nested, halving and hidden loops
Explain why vector::push_back is amortized O(1) yet occasionally O(n), and when to call reserve()
Recognise the harmonic sum n/1 + n/2 + ... + n/n = O(n log n) in loops over multiples

Chapters

PreviousHow a Judge Works and the Complexity Budget NextC++ for Competitive Programming