Did you know there's a way to measure how efficient your code is?

Imagine you and your friend are solving the same programming problem. You both write different code, and both programs produce the correct answer.

Now the question is... which code is better?

You might think, "That's easy! Just run both programs and see which one finishes first." But there's a problem.

The speed of a program doesn't depend only on the code. It also depends on many other factors, such as the computer you're using, the processor (CPU), the programming language, and other applications running in the background.

For example, the same program might finish in 1 second on one computer but 3 seconds on another.

So measuring a program using seconds isn't a fair way to compare algorithms.

Instead, developers measure how the number of steps an algorithm performs changes as the input size increases. This is called time complexity.

Think about counting numbers. If I ask you to count from 1 to 5, you'll finish almost instantly. But what if I ask you to count from 1 to 1,000,000? It'll take much longer because there are many more numbers to count.

Algorithms work in the same way. Some algorithms need only a few extra steps as the input grows, while others need significantly more.

To describe this growth, programmers use something called Big O notation. Big O is simply a way of describing how the number of steps grows as the input size grows.

In this lesson, you'll learn the four most common time complexities.

O(1) — Constant Time

Let's start with the simplest time complexity: O(1).

Imagine you have a box with 10 chocolates. Now your friend asks, "Can you give me the first chocolate?"

You simply open the box, pick the first chocolate, and hand it over. That took just one step.

Now let's make the box much bigger. Instead of 10 chocolates, imagine it contains 100 chocolates. Your friend asks the exact same question: "Can you give me the first chocolate?"

Does anything change? Not at all. You still open the box and pick the first chocolate. Even though the number of chocolates increased from 10 to 100, the number of steps stayed exactly the same.

What if the box had 1,000 chocolates? You'd still perform the same one step — pick the first chocolate.

This is called constant time, written as O(1). In O(1), the input size can grow, but the number of steps always stays the same.

Remember
In O(1), no matter how large the input becomes, the number of steps never changes.

O(n) — Linear Time

Now let's look at O(n).

Imagine you own a small coffee shop. One morning, 10 customers walk in. For every customer, you always do the same three things:

  1. Take their order.
  2. Make their coffee.
  3. Serve their coffee.

That's 3 steps for each customer. So for 10 customers, you perform 30 steps.

The next day, your coffee shop goes viral! Now 100 customers walk in. Do you still perform only 30 steps? Of course not. Now you perform 300 steps.

What if n customers walk into your coffee shop? Since each customer requires 3 steps, you'll perform 3n steps.

Notice something interesting. As the number of customers increases, the number of steps increases at the same rate. If the number of customers doubles, the number of steps also doubles.

In Big O notation, we're not interested in the exact number of steps. We're interested in how the number of steps grows. Since 3n grows at the same rate as n, we ignore the constant 3 and simply write the time complexity as O(n).

This is called linear time because the number of steps grows linearly with the input size.

O(n) Linear Time — coffee shop example showing 3 steps per customer O(n) Linear Growth graph showing steps increasing at a constant rate
Remember
In O(n), as the input size increases, the number of steps also increases at the same rate.

O(log n) — Logarithmic Time

Now let's look at O(log n).

Imagine you lose your glasses somewhere in your house. At first, you start searching randomly — under the bed, inside the wardrobe, behind the sofa.

After a while, you remember something. "Wait... I was upstairs the last time I was wearing my glasses!" Immediately, you stop searching downstairs. You've just eliminated half of the places you needed to search.

Then you remember something else. "I was studying in my bedroom." Now you can ignore all the other rooms upstairs and search only the bedroom. A few seconds later, you spot your glasses sitting on your study table.

Notice what happened. Instead of searching every possible place, each memory helped you eliminate a large part of the remaining search area. This is exactly how O(log n) works — rather than checking every item one by one, we repeatedly eliminate a large portion of the remaining data.

Let's look at a few examples:

  • 8 possible places → about 3 steps
  • 16 possible places → about 4 steps
  • 32 possible places → about 5 steps

Notice that every time the number of possible places doubles, the number of steps increases by only one.

Now imagine there are 1,000 possible places where your glasses could be. Would it take 1,000 steps to find them? Not at all. By eliminating half of the remaining places in every step, you would find your glasses in only about 10 steps.

That's why O(log n) is considered one of the fastest time complexities. Even when the input becomes much larger, the number of steps grows very slowly.

Remember
In O(log n), we eliminate a large portion of the remaining data in every step, so the number of steps grows very slowly as the input size increases.

O(n²) — Quadratic Time

Now let's look at O(n²).

Imagine you discover 5 treasure chests. Next to them, you find 5 keys. The problem is, you don't know which key opens which chest.

So you pick up the first chest and start trying the keys one by one until it opens. Then you move to the second chest and try all the keys again. Then the third. Then the fourth. And finally, the fifth.

For every chest, you may have to try every key.

Now imagine there are 100 treasure chests and 100 keys. For every new chest, you may have to try every key again. If there are n treasure chests and n keys, you'll perform up to n × n attempts. We write this as n².

Let's look at a few examples:

  • 5 chests → up to 25 attempts
  • 10 chests → up to 100 attempts
  • 100 chests → up to 10,000 attempts

Notice how quickly the number of attempts increases. When the number of chests doubles, the amount of work becomes much more than double. That's why algorithms with O(n²) work well for small inputs but can become very slow as the input size grows.

Remember
In O(n²), for every input, you go through all the inputs again. As the input size grows, the number of steps grows much faster than the input itself.

Summary

You've just learned the four most common time complexities you'll see in Data Structures and Algorithms. Here's a quick recap.

Time Complexity Name Real-Life Example
O(1) Constant Time Picking the first chocolate from a box
O(log n) Logarithmic Time Finding your glasses by eliminating half the search area each time
O(n) Linear Time Serving customers in a coffee shop
O(n²) Quadratic Time Trying every key on every treasure chest

Remember, time complexity doesn't tell us exactly how many seconds an algorithm takes to run. Instead, it tells us how the number of steps grows as the input size grows.

When the input size is small, two different algorithms might seem equally fast. But as the input becomes larger, choosing the right algorithm can make a huge difference. That's why developers use Big O notation — it gives us a simple way to compare algorithms and understand how well they'll perform as the amount of data increases.

As you continue learning Data Structures and Algorithms, you'll keep seeing these time complexities again and again. Now that you understand what they mean, you'll have a much easier time understanding and comparing algorithms.