Click image to open full size
Computer Science
Algorithms and Complexity
Sorting, searching, and Big-O efficiency
Related Tools
Related Labs
Related Worksheets
Related Cheat Sheets
Algorithms are step-by-step procedures for solving problems, from sorting a list to finding the shortest path on a map. Complexity describes how much time or memory an algorithm needs as the input size grows. This matters because two correct programs can behave very differently when given large data sets. Computer scientists use complexity to predict performance before running code.
Key Facts
- Linear search checks items one by one, so its time complexity is O(n).
- Binary search on a sorted list has time complexity O(log n).
- A simple nested loop over n items often has time complexity O(n^2).
- Big O notation describes an upper bound on growth rate as input size becomes large.
- If an algorithm does c steps per item, then T(n) = cn + k is simplified to O(n).
- Common growth order from fastest to slowest is O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n).
Vocabulary
- Algorithm
- An algorithm is a finite set of clear steps used to solve a problem or complete a task.
- Time complexity
- Time complexity describes how the number of operations grows as the input size increases.
- Space complexity
- Space complexity describes how much memory an algorithm uses as the input size increases.
- Big O notation
- Big O notation expresses the approximate upper growth rate of an algorithm while ignoring constants and smaller terms.
- Input size
- Input size is the amount of data an algorithm must process, often represented by n.
Common Mistakes to Avoid
- Counting seconds instead of operations is wrong because running time depends on hardware, language, and implementation details.
- Keeping constant factors in Big O is wrong because O(3n + 10) simplifies to O(n) for large-input growth analysis.
- Assuming every loop makes an algorithm O(n) is wrong because nested loops, halving loops, and early exits can change the growth rate.
- Ignoring the input requirements is wrong because binary search is O(log n) only when the data is already sorted.
Practice Questions
- 1 An algorithm performs 5n + 20 operations. What is its Big O time complexity, and about how many operations does it perform when n = 100?
- 2 A nested-loop algorithm compares every pair in a list, taking about n^2 operations. How many operations occur for n = 50, and how many for n = 200?
- 3 You need to search for a name in a phone book that is already alphabetized. Explain why binary search is more efficient than linear search for a very large phone book.