What is the time complexity of an algorithm?

Think of it using an analogy: Imagine you have to find a name in a phone book with $n$ names. * $\mathcal{O}(n)$ (Linear): You look at every single name one by one until you find it. If the book doubles in size, the time it takes also doubles. * $\mathcal{O}(\log n)$ (Logarithmic): You open the book in the middle and decide if your name is in the first half or second half. You repeat this process. If the book doubles in size, you only have to do one more check. This is much, much faster as $n$ gets huge. So, time complexity is essentially the scalability blueprint for an algorithm!

As a programmer, I can tell you that Time Complexity is probably the single most important concept in algorithm analysis! ### Definition Time complexity is a measure of the amount of time an algorithm takes to run as a function of the length of the input (n). Crucially, it doesn't measure the time in seconds (since that depends on the computer's speed), but rather the rate of growth of the algorithm's runtime as the input size ($n$) increases. ### Big O Notation We usually express time complexity using Big O Notation (e.g., $\mathcal{O}(n)$, $\mathcal{O}(n^2)$). This notation simplifies the analysis by ignoring constant factors and lower-order terms, focusing only on the worst-case or upper bound growth rate. | Big O Notation | Meaning | Example | | :--- | :--- | :--- | | $\mathcal{O}(1)$ | Constant Time (Fastest) | Accessing an array element. | | $\mathcal{O}(\log n)$ | Logarithmic Time | Binary Search (cutting the problem in half each time). | | $\mathcal{O}(n)$ | Linear Time | Simple loop (e.g., searching an unsorted array). | | $\mathcal{O}(n^2)$ | Quadratic Time (Slow) | Nested loops (e.g., Bubble Sort). | The goal of any good computer scientist is to design an algorithm with the lowest possible time complexity to ensure it remains fast even with massive inputs.