Prof. Bolts Complexity Studio
Prof. Bolts
Analyse your own function
Sum of an array
Linear search, worst case
Two loops in a row
Nested loops
Inner loop up to i
Halving loop
Constant time
Steps as cubes: one loop
Steps as cubes: nested loops
Steps as cubes: bubble sort
Steps as cubes: binary search
Which function grows fastest?
Prove 3n² + 5n + 2 is O(n²)
Prove 2n + 10 is O(n)
Prove 3n² + 5n + 2 is Ω(n²)
Prove ½n² − 3n is Θ(n²)
Show n³ is not O(n²)
Limit method: Θ example
Limit method: n log n vs n²
Loop invariant of insertion sort
Bubble sort
Selection sort
Insertion sort
How recursion runs: fact(4)
Recurrence for factorial
Recurrence for binary search
Recurrence for merge sort
Iteration: T(n − 1) + c
Iteration: T(n/2) + c
Iteration: 2T(n/2) + n
Substitution: O(n log n)
Substitution: O(n²)
Substitution: O(log n)
Recursion tree: 2T(n/2) + n
Recursion tree: 3T(n/4) + n²
Recursion tree: 4T(n/2) + n
Master Theorem: case 2
Master Theorem: binary search
Master Theorem: case 1
Master Theorem: case 3
Build a BST
Search
Minimum and maximum
Successor
Predecessor
Delete a leaf
Delete a node with one child
Delete a node with two children
Inorder traversal
Preorder traversal
Postorder traversal
← Previous
Next →
All animations