Analysis and searching

How to count the cost of an algorithm by reading its loops, and how binary search finds an item in a sorted array in about log₂ n steps.

About 6 hours of study

Learning objectives

• Read the Big-O of common loop shapes
• Tell the best, worst and average case apart
• Write binary search with a correct stopping rule
• Use lower_bound to count copies and find insertion points

Lessons

1. 1

   Analysing algorithms

   Count the steps an algorithm takes, read Big-O from loop shapes, and see how fast n², n log n and log n grow.

2. 2

   Binary search

   Halve a sorted range until the key is found, find the first position of a value, and get the boundaries right.

Module practice

• Count the loop stepsEasy
• Two ways to find a pairMedium
• Pairs with a sum divisible by kHard
• Binary searchEasy
• Count numbers in a rangeMedium
• The smallest truck that will doHard

Sorting ›