Frequency Count Method

In the previous lesson, we learned that time complexity tells us how the number of steps an algorithm takes changes as the input size grows.

But before we can talk about time complexity, we need to answer one simple question.

How many steps does an algorithm actually perform?

We don't guess the answer.

We count it.

That's exactly what the Frequency Count Method helps us do.

The idea is simple.

We count the number of steps a program takes to execute.

Once we know the total number of steps, finding the time complexity becomes much easier.

Our Assumption

Before we start counting, we'll make one assumption.

Every simple statement counts as one step.

This keeps things consistent and makes algorithms much easier to analyze.

For example,

int x = 10;

counts as 1 step.

Similarly,

sum += x;

also counts as 1 step.

We're not measuring seconds or milliseconds.

Instead, we're simply counting how much work the program performs.

You can think of it like keeping score.

Every step adds one point.

The final score tells us how much work the program had to do.

Example 1 — Statements That Execute Once

We'll start with the simplest kind of program.

void greet() {
    cout << "Hello";
    cout << "Welcome";
    cout << "Have a great day!";
}

Every statement executes exactly once.

Let's count the frequency of each statement.

Adding the frequencies together gives us

So the time function is

f(n) = 3

The time function represents the total number of steps performed by the program.

Here, the program always performs 3 steps.

It doesn't matter whether the input size is 10, 100, or even 1,000,000. The number of steps never changes.

When the number of steps stays the same as the input size grows, we say the growth is constant.

In the previous lesson, we learned that Big O notation describes how the number of steps grows as the input size grows.

To write Big O notation, write the letter O, then write the growth inside round brackets.

Since the growth is constant, we write

O(1)

The 1 doesn't mean the algorithm performs one step.

It simply represents constant growth.

Whether an algorithm always performs 3 steps, 20 steps, or 500 steps, its time complexity is still O(1) because the number of steps never change as the input size grows.

What Happens When a Statement Executes Multiple Times?

The previous example was straightforward because every statement executed only once.

Real programs are rarely that simple.

Most programs contain loops, where the same statement executes again and again.

Instead of counting the statement once, we count how many times the loop executes it.

That's the only thing that changes.

Let's look at an example.

Example 2 — A Single Loop

int sum = 0;

for (int i = 0; i < n; i++) {
    sum += i;
}

To keep the counting simple, let's start with n = 5.

That means the loop executes 5 times.

Now let's count the frequency of each statement.

Adding the frequencies together gives us

1 + 5 = 6

So,

f(5) = 6

Of course, the input won't always be 5.

It could be 10, 100, or even 1,000.

Instead of writing a different answer for every possible input, we simply replace 5 with n.

This gives us the time function.

f(n) = n + 1

Now it's time to find the time complexity.

Our time function has two terms.

• n
• 1

To compare them, we look at their powers.

The term n can be written as n¹.

The constant 1 can be written as n⁰, because n⁰ = 1.

When finding the time complexity, we keep only the term with the highest power.

Here, 1 is greater than 0, so we keep n.

To write the time complexity, write the letter O, then write the remaining term inside round brackets.

O(n)

As the input size grows, the number of steps grows with n, so the algorithm has a time complexity of O(n).

What Happens With Nested Loops?

So far, we've counted statements that execute once and statements that execute inside a single loop.

Now it's time to level things up.

What happens when one loop is placed inside another?

At first glance, it might not seem very different.

After all, it's still just two loops.

But that second loop changes everything.

The inner loop doesn't execute just once. It executes every time the outer loop executes.

That's why nested loops usually perform much more work than a single loop.

Let's see why.

Example 3 — Nested Loops

int count = 0;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        count++;
    }
}

To keep the counting simple, let's start with n = 3.

The outer loop executes 3 times.

For every iteration of the outer loop, the inner loop also executes 3 times.

That means count++ executes

3 × 3 = 9

times.

Now let's count the frequency of each statement.

Adding the frequencies together gives us

1 + 9 = 10

So,

f(3) = 10

Just like the previous example, the input won't always be 3.

Replacing 3 with n gives us the following frequencies.

This gives us the time function.

f(n) = n² + 1

Now let's find the time complexity.

Our time function has two terms.

• n²
• 1

To compare them, we look at their powers.

The term n² has a power of 2.

The constant 1 can be written as n⁰, because n⁰ = 1.

When finding the time complexity, we keep only the term with the highest power.

Here, 2 is greater than 0, so we keep n².

To write the time complexity, write the letter O, then write the remaining term inside round brackets.

O(n²)

As the input size grows, the number of steps grows with n², so the algorithm has a time complexity of O(n²).

Example 4 — Guessing a Number Faster

Suppose I ask you to guess a number between 1 and 16.

How would you do it?

One way is to start from the beginning.

1, 2, 3, 4, 5...

You'll eventually find the correct number, but it could take a lot of guesses.

Now let's try a smarter approach.

Your first guess is the middle number.

8

If I say higher, you immediately know the number cannot be between 1 and 8.

So you can ignore all of them.

Now only these numbers are left.

9 to 16

Again, guess the middle.

12

If I say higher, you can ignore 9 to 12.

Now only these numbers are left.

13 to 16

Guess the middle again.

14

If I say lower, only these numbers remain.

13 to 14

One more guess, and you've found the answer.

Notice what happened?

You never checked every number.

With every guess, you eliminated half of the remaining possibilities.

Now let's count how many guesses this strategy takes.

Take a moment to look at the table.

Can you spot the pattern?

Every time the number of values doubles, we need only one extra guess.

Suppose there are n possible values, and it takes k guesses to find the answer.

After the first guess, half of the possibilities remain.

n/2

After the second guess,

n/4

After the third guess,

n/8

Can you spot the pattern?

After k guesses, the remaining possibilities are

n/2ᵏ

We stop when only one possibility remains.

So,

n/2ᵏ = 1

Multiplying both sides by 2ᵏ gives us

n = 2ᵏ

Now we need to find the value of k.

This is where logarithms help us.

A logarithm answers a simple question:

What power should I raise 2 to so that I get n?

For example,

2³ = 8

So,

log₂ 8 = 3

Similarly,

2⁴ = 16

So,

log₂ 16 = 4

Using the same idea,

n = 2ᵏ

becomes

k = log₂ n

Since k represents the number of guesses, the time function is

f(n) = log₂ n

To write the time complexity, write the letter O, then write the growth inside round brackets.

O(log₂ n)

In Big O notation, we usually omit the base 2, so we simply write

O(log n)