← Discover
Algorithms
Big-O Complexity
10 terms · by ineedtostudy · updated 4 hours ago
Sign up or log in to track what you have mastered. You can still study this set as a guest.
Flashcards
Flip through the deck and sort each card into “still learning” or “got it”.
Learn
Adaptive rounds — multiple choice first, then typing, weakest cards more often.
Match
Race the clock pairing terms with definitions. Six pairs a round.
Test
A graded mock exam: written, multiple choice and true/false, marked at the end.
Crossword
Terms become answers, definitions become clues. Solve it here or print it.
Terms in this set
O(1)
Constant. Runtime does not depend on input size. Array index, hash table lookup on average.
O(log n)
Logarithmic. Halves the problem each step. Binary search, balanced tree lookup.
O(n)
Linear. One pass over the input. Finding the maximum of an unsorted array.
O(n log n)
Linearithmic. The lower bound for comparison sorting. Mergesort, heapsort, average quicksort.
O(n²)
Quadratic. Nested loops over the input. Bubble sort, insertion sort, naive pair comparison.
O(2ⁿ)
Exponential. Adding one element doubles the work. Naive recursive subset enumeration.
O(n!)
Factorial. Every permutation. Brute-force travelling salesman.
Amortised complexity
The average cost per operation across a sequence. Appending to a dynamic array is amortised O(1) despite occasional O(n) resizes.
Best, average, worst case
Quicksort is O(n log n) average but O(n²) worst case when the pivot is always extreme.
Space complexity
Extra memory as a function of input size. Mergesort needs O(n); heapsort sorts in place at O(1).