Time Complexity
What is Time Complexity?
Time complexity is a way to describe how the runtime of an algorithm changes as the size of the input changes. It's a crucial concept in computer science because it helps us understand the efficiency of our algorithms, especially when dealing with large datasets.
Why is Time Complexity Important?
Imagine two algorithms that solve the same problem, but one takes seconds while the other takes hours as the input size grows. Time complexity allows us to predict this behavior and choose the more efficient algorithm.
Basic Example
Consider two different ways to sum the first n natural numbers:
-
Loop-based approach:
Comparing Time Complexities
| Algorithm | Time Complexity | Description |
|---|
| Loop | O(n) | Grows linearly with n |
| Formula | O(1) | Always takes constant time |
- Note - Don't worry, if you don't understand this, we will be diving deep into this in upcoming chapters
