Introduction to algorithms - Binary search Flashcards
What is an algorithm?
A set of instructions for accomplishing a task.
What is binary search?
An algorithm that takes a sorted list as input and returns the position of the target element (or null if not found).
How does binary search work?
It guesses the middle element and eliminates half the remaining numbers each time.
For a list of size n, how many steps does binary search take?
log₂ n steps in the worst case.
What does ‘linear time’ mean?
The maximum number of operations is the same as the size of the list (n).
What type of time complexity does binary search have?
Logarithmic time (or log time) - O(log n).
How do the run times of binary search and simple search grow differently?
Binary search takes a little more time, but simple search takes a lot more time as input size increases.
What does Big O notation tell you?
How fast an algorithm is by measuring the growth in number of operations as input size increases.
What is the Big O notation for simple search?
O(n) - linear time.
What is the Big O notation for binary search?
O(log n) - logarithmic time.
What does Big O establish about an algorithm?
The worst-case run time.
Name the five common Big O run times from fastest to slowest.
- O(log n)
- O(n)
- O(n * log n)
- O(n²)
- O(n!)
What is factorial time O(n!)?
Run time where the number of operations is n factorial, like the traveling salesperson problem.
