3.4.1.1 Big O Notation
Algorithms and Problem Solving
Big O notation is a mathematical way to describe the time complexity of an algorithm. It provides an upper bound on the time an algorithm will take to complete as the input size grows. This notation helps in comparing the efficiency of different algorithms by giving a clear picture of their performance.
How Big O Notation Works
Big O notation uses symbols to describe how the runtime of an algorithm changes with the size of the input. Here are some common examples:
- O(1) Constant Time: The runtime does not change with the size of the input. For instance, accessing a specific item in an array by its index is constant time because it takes the same amount of time regardless of the array size.
- O(n) Linear Time: The runtime grows linearly with the size of the input. For example, consider a scenario where there are n students in a college, each with a unique student ID. If we need to find a specific student by searching through the list of all n students, the time it takes to find the student will depend on the number of students we have to check. In the worst-case scenario, the student we are looking for might be the very last one on the list, meaning we would have to check all n students. This process involves examining each student one by one, making the search take a time proportional to n. Therefore, this example represents a linear time complexity O(n), where the time taken increases directly with the number of students.
- O(n²) Quadratic Time: The runtime grows quadratically as the size of the input increases. For instance, consider a scenario where n students in a college are participating in a programming competition, and we want to compare the performance of each pair of students to determine the best team. To do this, we must compare each student with every other student. The number of comparisons required is the sum of the first n - 1 integers, which can be approximated as