← Introduction to Computer Science

Unit 13: Algorithm Analysis and Big-O

Measuring how an algorithm's work grows instead of timing it once, and the handful of curves everything eventually reduces to.

7 topics · 24 questions

Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.

Measuring Growth Instead of Timing an Algorithm

  1. How it worksHow does counting basic operations as input size grows describe an algorithm independent of any machine?
  2. Common mistakeWhy isn't a faster computer a real fix for an algorithm with bad growth?
  3. Going furtherWhat happens to a linear-time algorithm's runtime once the input size grows from a thousand to a million?
Your turn1 of 2
An algorithm performs 14 basic operations per input item. For an input of size 6493, how many total basic operations does it perform?

Big-O as an Upper Bound

  1. How it worksHow does Big-O describe the slowest an algorithm's growth could possibly be as input size climbs?
  2. Worked exampleFind the Big-O of a loop that runs n times followed by a separate loop that also runs n times.
  3. Common mistakeWhy doesn't Big-O tell you the actual runtime in seconds for a given input?
  4. Going furtherWhat happens to Big-O classification once a constant factor like 100n is compared against n2?
Your turn1 of 2
Find the total operation count for a loop that runs 6964 times followed by a separate loop that also runs n times, computed as n plus n.

Big-Omega and Big-Theta

  1. How it worksHow does Big-Omega describe a lower bound while Big-Theta pins growth down tightly from both sides?
  2. Worked exampleFind the Big-Omega, Big-O, and Big-Theta of a loop that always runs exactly n times no matter the input.
  3. Going furtherWhat happens to an algorithm's Big-Theta when its best case and worst case grow at different rates?
Your turn1 of 2
Find the Big-Omega, Big-O, and Big-Theta of a loop that always runs exactly 6964 times no matter the input, expressed as a single operation count.

Best Case, Average Case, and Worst Case

  1. How it worksHow does linear search's best case find the target immediately while its worst case checks every element?
  2. Worked exampleFind the best-case and worst-case number of comparisons for a linear search over 10 elements.
  3. Common mistakeWhy doesn't an algorithm's average case fall exactly halfway between its best and worst case?
Your turn1 of 2
Find the worst-case number of comparisons for a linear search over 697 elements when the target is not present at all.

Comparing Growth Curves: n, n log n, n2, and 2n

  1. How it worksHow do the curves for n, n log n, n2, and 2n spread apart from each other as n keeps growing?
  2. Worked exampleFind the number of operations n, n log n, n2, and 2n each predict at n = 20.
  3. Going furtherWhat input size makes a 2n algorithm cross one second when an n2 algorithm is still nearly instant?
  4. Common mistakeWhy doesn't a bigger constant in front of n always beat a worse growth rate like n2?
  5. Ties togetherHow does marking where 2n crosses n2 explain why brute-force search is abandoned on large inputs?
Your turn1 of 2
Find the number of operations n2 predicts at n = 6965.

Amortized Analysis: A Dynamic Array Doubling

  1. How it worksHow does a dynamic array doubling its capacity spread the cost of resizing across many cheap appends?
  2. Worked exampleTrace the cost of eight appends into a dynamic array that starts at capacity 1 and doubles when it fills.
  3. Common mistakeWhy doesn't one expensive resize mean every append into a dynamic array is expensive?
Your turn1 of 2
A dynamic array starts at capacity 1 and doubles each time it fills, for 14 doublings total. What is its capacity after these k doublings, computed as 2 to the power of k?

Space Complexity

  1. How it worksHow does space complexity count the extra memory an algorithm uses beyond its input, as that input grows?
  2. Worked exampleFind the space complexity of an iterative sum versus a recursive sum over a list of n elements.
  3. Ties togetherHow does the space cost of a recursive call stack connect back to why deep recursion can crash a program?
Your turn1 of 2
An iterative sum over a list of 6964 elements uses constant extra space, while a naive recursive sum uses one stack frame per element. How many extra stack frames does the recursive version use for a list of n elements?