Imagine you have two different recipes for baking a cake. Both recipes produce a delicious cake, but one takes 20 minutes and the other takes two hours. Which one would you choose? Most likely, the faster one. Algorithms are like recipes for computers. They are a set of instructions to solve a problem. Just like with recipes, there can be many different algorithms to solve the same problem, and some are much more efficient than others.

But how do we measure an algorithm's efficiency? We can't just time it with a stopwatch. The same algorithm will run faster on a supercomputer than on an old laptop. The programming language used can also affect the speed. We need a way to talk about an algorithm's performance that is independent of the hardware or specific software environment.

This is where algorithm analysis comes in. We focus on two key resources: time and space.

• Time complexity is how much time an algorithm takes to run, relative to the size of its input.
• Space complexity is how much memory an algorithm needs, relative to the size of its input.

The "size of the input" is a crucial idea. We'll often call it 'n'. If we're sorting a list of 10 items, n is 10. If we're sorting a million items, n is a million. We want to know how the running time or memory usage changes as 'n' gets bigger.

To describe complexity in a standardized way, we use a mathematical language called asymptotic notation. It describes the behavior of an algorithm as the input size approaches infinity. This helps us focus on the big picture of how an algorithm scales, ignoring constant factors and less significant terms that don't matter as 'n' gets very large.

There are three main types of notation you'll encounter.

Big O is the most commonly used notation because we're often most concerned with an algorithm's worst-case performance. It's like a promise: "This algorithm will never be slower than this."

Big Omega (Ω) gives us the floor. It's the promise from the other direction: "This algorithm will never be faster than this."

When you can use Big Theta (Θ), you have a very precise understanding of an algorithm's performance. It says, "This algorithm's growth rate is exactly this."

Let's see how to apply this to actual algorithms. We'll start with simple, non-recursive ones.

Iterative algorithms use loops. To find their complexity, we count how many times the core operations inside the loops are executed. Consider this simple function to find the largest number in a list.

If the list numbers has n elements, the loop runs n times. Inside the loop, we do a constant number of operations (a comparison and maybe an assignment). So, the total number of operations is roughly proportional to n. We express this as $O(n)$, which is called linear time. If the list doubles in size, the runtime roughly doubles.

Recursive algorithms call themselves. Analyzing them can be trickier. We need to figure out how many times the function calls itself and how much work it does in each call.

A classic example is the factorial function.

To compute factorial(n), the function calls factorial(n-1), which calls factorial(n-2), and so on, until it reaches factorial(0). This creates a chain of n calls. Each call does a constant amount of work (one multiplication and one subtraction). Therefore, the time complexity is also $O(n)$.

An algorithm might not always take the same amount of time for inputs of the same size. For example, searching for an item in a list. If the item is at the very beginning, you find it immediately. If it's at the end, you have to check every single element.

This leads to three scenarios:

Big O notation typically describes the worst-case scenario because it provides a reliable upper limit on performance. Average-case analysis is often more complex but can be very useful for understanding how an algorithm performs in practice.

For recursive algorithms, we can formalize our analysis using a recurrence relation. This is an equation that defines a function in terms of its own value on smaller inputs. For the factorial function, the recurrence relation for the number of operations, $T(n)$, is:

We also need a base case: $T(0) = 1$, since factorial(0) takes constant time. Solving this recurrence relation confirms that the complexity is $O(n)$. For more complex recursive algorithms, like those that divide a problem into smaller pieces, solving these relations is key to finding the overall complexity.

Algorithm analysis is a fundamental skill. By understanding time and space complexity and using tools like Big O notation, you can make informed choices about which algorithms to use and write more efficient code.