Computer Science · Ch 5 — Sorting
Time Complexity of Algorithms
Time Complexity of Algorithms
Why Time Complexity Matters
When you write a program to solve a problem, there is often more than one way to do it. You saw this in Class XI when you compared four different algorithms to check whether a given number is prime. For the same problem, one algorithm may take much longer to run than another. The amount of time an algorithm takes to process a given set of data is called its time complexity.
In the small examples used in this chapter — lists of just a few elements — the time and memory used by bubble sort, selection sort, and insertion sort do not differ much. But in the real world, sorting algorithms must handle huge amounts of data. When you are sorting millions of records, the total time taken becomes a critical factor. That is why computer scientists who design sorting techniques always want to know the time complexity of their algorithms. The goal is to understand how a sorting algorithm behaves when the order of input elements changes, or when the number of elements in the list increases or decreases. This kind of comparison helps decide which algorithm is best suited for a particular kind of data and application.
Estimating Time Complexity — The Basics
Calculating the exact complexity of different algorithms involves detailed mathematical analysis, which is beyond the scope of this textbook. However, you can get a good working idea from a few simple rules.
The time complexity of an algorithm is estimated by looking at its loops. The number of times the innermost statements execute is the key factor.
Here are the basic rules:
- Constant time algorithms: Any algorithm that does not have any loop will have a time complexity of 1. The number of instructions to be executed is constant, no matter how large the data size is.
- Linear time algorithms: Any algorithm that has a single loop (usually running from 1 to n) will have a time complexity of n. The loop executes the statement inside its body n times.
- Quadratic time algorithms: A loop within a loop (a nested loop) will have a time complexity of n².
- Dominant term: If an algorithm has both a nested loop and a single loop, the time complexity is estimated based on the nested loop only — because it dominates the total time.