LearningGamesGlossaryFlashcardsReviseToolsCourses
Simulators

Big O Complexity Playground

A-Level
Prerequisite: Data must be sorted
Target29
2
0
29
1
43
2
53
3
61
4
62
5
71
6
95
7
97
8
Searching a sorted list of 9 values for 29.

Comparisons

0

Passes

0

Binary SearchO(log n)average case
▶FUNCTION binarySearch(array, target)
▶low ← 0
▶high ← LENGTH(array) − 1
▶WHILE low ≤ highPasses
▶mid ← (low + high) DIV 2
▶IF array[mid] = target THENComparisons
▶RETURN mid
▶ELSE IF array[mid] < target THENComparisons
▶low ← mid + 1
▶ELSE
▶high ← mid − 1
▶ENDIF
▶ENDWHILE
▶RETURN −1
▶ENDFUNCTION

What is being counted

  • •Comparisons: two values tested against each other.
  • •Passes: one run of the main loop.

Big O describes how this work grows as the input gets bigger. It is not a count of instructions.

Step 1 / 12