Back to Mathematical Foundations
AdvancedAdults
Big O Notation
How do we measure how "fast" an algorithm is? We use Big O notation. It doesn't measure time in seconds, but rather how the runtime of an algorithm grows as the input size grows.
**O(1) - Constant Time:** The runtime is the same, no matter the size of the input.
- Example: Accessing an item in an array by its index (
**O(n) - Linear Time:** The runtime grows linearly with the input size 'n'.
- Example: Looping through every item in a list once. If the list has 10 items, it takes 10 "steps". If it has 1,000,000 items, it takes 1,000,000 "steps".
**O(n²) - Quadratic Time:** The runtime grows by the square of the input size. This is common in algorithms with nested loops.
- Example: Comparing every item in a list to every other item.
**O(log n) - Logarithmic Time:** The runtime grows very slowly. Every time you double the input size, you only add one "step" to the work.
- Example: Binary search in a sorted array.
Understanding Big O is crucial for writing efficient code, especially when working with large datasets.
**O(1) - Constant Time:** The runtime is the same, no matter the size of the input.
- Example: Accessing an item in an array by its index (
my_array[5]).**O(n) - Linear Time:** The runtime grows linearly with the input size 'n'.
- Example: Looping through every item in a list once. If the list has 10 items, it takes 10 "steps". If it has 1,000,000 items, it takes 1,000,000 "steps".
**O(n²) - Quadratic Time:** The runtime grows by the square of the input size. This is common in algorithms with nested loops.
- Example: Comparing every item in a list to every other item.
**O(log n) - Logarithmic Time:** The runtime grows very slowly. Every time you double the input size, you only add one "step" to the work.
- Example: Binary search in a sorted array.
Understanding Big O is crucial for writing efficient code, especially when working with large datasets.
Identify the Big O
Look at the `find_duplicates` function. What is its Big O time complexity? Assign your answer as a string to the `big_o_complexity` variable (e.g., "O(n)").