3.4.1 Time Complexity
Algorithms and Problem Solving
Time complexity is a measure of how the runtime of an algorithm increases as the size of the input data grows. It helps us understand how efficiently an algorithm performs when dealing with larger amounts of data.
Example: Consider the task of sorting a list of numbers. If the list has only a few numbers, the task might be quick. However, as the volume of numbers increases, the time required to sort them also increases. Time complexity allows us to predict how this runtime will grow as the size of the list becomes larger.
3.4.1.1 Big O Notation
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.