Understanding Algorithm Time Complexity

When we write a program, our first goal is usually simple:

Make the program produce the correct answer.

But as programs become larger and start working with thousands or millions of values, another question becomes equally important:

How much work does the program have to do to produce that answer?

Two programs can produce the same result while using completely different amounts of work.

One may finish almost instantly. Another may become slower and slower as the amount of data increases. This idea is called algorithm running time.

In this article, we are not yet trying to memorize Big O notation. Before learning symbols such as O(n) and O(log n), we first need to understand what an algorithm is actually doing when its input becomes larger.

4.1 Learning Objectives

By the end of this article, you should understand:

• what algorithm running time means
• what input size means
• why programmers use n
• why running time is not simply measured in seconds
• how to count important operations
• how loops affect the amount of work
• why two correct algorithms can perform differently
• what growth rate means
• how running time prepares us for Big O notation

4.2 Before We Begin — Why Should You Care?

Imagine building a program that works perfectly with:

10 users

You test it, and everything feels fast.

Later, the same program becomes popular and starts handling:

10,000 users

Then:

1,000,000 users

Suddenly, some operations become slow. The code still produces the correct answer.

So what went wrong?

The problem may not be correctness.

The problem may be the amount of work the algorithm performs as the data grows.

This is why understanding running time is important.

4.2 A Real-Life Story

Before we look at code, it helps to connect algorithm running time with something familiar. In real life, many tasks feel easy with only a few items, but the same task can become much harder as the amount of data grows. This is exactly what happens with algorithms. A method that feels fast with five items may require far more work with five thousand. The following story illustrates this idea in a simple, memorable way.

Finding a Student’s Record

Imagine that you work in a school office. There are only five student files on a table:

Ali
Ahmed
Ayesha
Hassan
Sara

The principal asks:

“Please find Hassan’s file.”

You start checking from the beginning.

Ali      → No
Ahmed    → No
Ayesha   → No
Hassan   → Found

You checked four files.

That was easy.

Now imagine the school has:

5,000 students

and the files are not arranged in any useful order.

You may need to inspect:

10 files
500 files
2,000 files
or even all 5,000 files

The task is still the same:

Find one student’s file.

But the amount of data has increased.

And because the data increased, the amount of work may also increase.

That is the basic idea behind algorithm running time.

4.4 What Is an Algorithm?

An algorithm is a sequence of steps used to solve a problem.

Suppose we want to find whether the number 18 exists in this array:

4   7   12   18   25

One simple algorithm is:

1. Start from the first number.
2. Compare it with 18.
3. If it matches, stop.
4. Otherwise, move to the next number.
5. Continue until the number is found or the array ends.

In C#:

static bool ContainsNumber(int[] numbers, int target)
{
    for (int i = 0; i < numbers.Length; i++)
    {
        if (numbers[i] == target)
        {
            return true;
        }
    }

   return false;
}

The code is simply an implementation of the algorithm.

4.5 What Is Algorithm Running Time?

The term running time may sound like:

“How many seconds does the program take?”

But in algorithm analysis, we are more interested in:

How much work does the algorithm perform as the amount of input increases?

Consider:

static void PrintNumbers(int[] numbers)
{
    foreach (int number in numbers)
    {
        Console.WriteLine(number);
    }
}

If the array contains:

5 numbers

the loop runs about:

5 times

If it contains:

100 numbers

the loop runs about:

100 times

If it contains:

1,000,000 numbers

the loop runs about:

1,000,000 times

The important observation is:

More input causes more work.

4.6 What Is Input Size?

4.6 What Is Input Size?

The input size is the amount of data given to an algorithm.

Suppose we have:

int[] numbers = { 10, 20, 30, 40, 50 };

The array contains:

5 elements

Therefore, the input size is:

5

If the array contains:

10,000 elements

then the input size is:

10,000

Many algorithms perform more work when this number becomes larger.

4.7 Why Programmers Use n

Instead of repeatedly saying:

“the number of elements in the input”

programmers usually represent the input size using:

n

For example:

5 elements
→ n = 5

100 elements
→ n = 100

1,000,000 elements
→ n = 1,000,000

Whenever you see n, think:

How much data does the algorithm have to process?

For example:

n students
n products
n players
n scores
n messages

For an array:

int[] scores = { 65, 82, 91, 75, 88 };

we can think of:

n = scores.Length

Here:

n = 5

4.8 Running Time Does Not Simply Mean Seconds

Suppose we run the same program on two computers.

Computer A

Fast CPU
Modern hardware
Fast memory

Computer B

Older CPU
Slower hardware
Slower memory

The same program might take:

Computer A → 0.1 seconds
Computer B → 0.5 seconds

Did the algorithm change?

No.

The algorithm is exactly the same.

Only the hardware changed.

Actual execution time can also depend on:

• CPU speed
• memory
• operating system
• programming language
• compiler optimizations
• background applications
• runtime environment

Therefore, saying:

“My algorithm took 0.02 seconds.”

does not tell us enough about the algorithm itself.

A better question is:

How does its amount of work change when the input becomes larger?

4.9 Counting Operations Instead of Seconds

One useful way to study an algorithm is to count important operations.

Consider:

for (int i = 0; i < numbers.Length; i++)
{
    Console.WriteLine(numbers[i]);
}

If:

numbers.Length = 5

the important action occurs approximately:

5 times

If:

numbers.Length = 1,000

it occurs approximately:

1,000 times

An operation might be:

comparison
addition
array access
assignment
loop iteration

Which operation we count depends on the algorithm we are analyzing.

4.10 Example — Searching for a Number

Consider:

[8, 12, 4, 19, 31]

We want to find:

19

The algorithm checks from left to right.

Step 1

8 == 19?

No

Step 2

12 == 19?

NO

Step 3

4 == 19?

No

Step 4

19 == 19?

Yes

The algorithm performed:

4 comparisons

Now suppose we search for:

31

The algorithm performs:

5 comparisons

If we search for:

100

which does not exist, it still checks all five elements.

Get Mujeeb Ur Rehman’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

This shows that the same algorithm can perform different amounts of work depending on the input.

4.11 Linear Search in C#

The same search algorithm can be written as:

static int FindNumber(int[] numbers, int target)
{
    for (int i = 0; i < numbers.Length; i++)
    {
        if (numbers[i] == target)
        {
            return i;
        }
  return -1;
}

Example:

int[] numbers = { 8, 12, 4, 19, 31 };
int index = FindNumber(numbers, 19);
Console.WriteLine(index);

Output:

3

The most important part for running-time analysis is the loop:

for (int i = 0; i < numbers.Length; i++)

As the array grows, the algorithm may need to perform more comparisons.

Later, we will learn that algorithms like this are often described using Big O notation.

For now, just understand:

A larger input may cause more repeated work.

4.12 Not Every Operation Gets Slower When n Grows

Consider this function:

static int GetFirstScore(int[] scores)
{
    return scores[0];
}

Suppose the array contains:

5 scores

We access:

scores[0]

Now suppose it contains:

5,000,000 scores

We still access:

scores[0]

We do not need to inspect the other values.

So even though the input becomes much larger, the amount of work remains approximately the same.

Compare that with:

foreach (int score in scores)
{
    Console.WriteLine(score);
}

Here the algorithm processes every element.

These two pieces of code behave very differently as n grows.

4.13 Same Problem, Different Algorithms

One of the most important ideas in computer science is:

There is often more than one way to solve the same problem.

Suppose we want to calculate:

1 + 2 + 3 + ... + n

For:

n = 5

the answer is:

1 + 2 + 3 + 4 + 5 = 15

We can solve this problem in different ways.

Approach 1 — Add Every Number

static long CalculateSum(long n)
{
    long sum = 0;

  for (long i = 1; i <= n; i++)
    {
        sum += i;
    }
    return sum;
}

For:

n = 5

the loop performs:

5 iterations

For:

n = 100

it performs:

100 iterations

For:

n = 1,000,000

it performs:

1,000,000 iterations

The amount of work increases as n increases.

Approach 2 — Use a Formula

We can calculate the same sum using:

n × (n + 1)
───────────
     2

In C#:

static long CalculateSum(long n)
{
    return n * (n + 1) / 2;
}

If:

n = 5

we calculate the answer directly.

If:

n = 1,000

we still calculate it directly.

If:

n = 1,000,000

we still use only a small fixed number of arithmetic operations.

Both approaches return the same answer.

But they require very different amounts of work.

This leads to an important question:

Can we solve the same problem with less work?

4.14 Nested Loops Can Grow Much Faster

Consider:

static void PrintPairs(int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            Console.WriteLine($"{i}, {j}");
        }
    }
}

There are two loops.

For every iteration of the outer loop, the inner loop runs n times.

Look at what happens:

n = 2
→ 4 pairs

n = 3
→ 9 pairs

n = 10
→ 100 pairs

n = 100
→ 10,000 pairs

n = 1,000
→ 1,000,000 pairs

This algorithm grows much faster than a single loop.

Compare:

Single loop

n = 10      → about 10 operations
n = 100     → about 100 operations
n = 1,000   → about 1,000 operations

With:

Two full nested loops

n = 10      → about 100 operations
n = 100     → about 10,000 operations
n = 1,000   → about 1,000,000 operations

This difference in how quickly the work increases is called the algorithm’s growth rate

4.15 Lines of Code Do Not Tell Us Running Time

Consider:

int first = numbers[0];

This directly accesses one element.

Now consider:

Array.Sort(numbers);

Both appear to be one line of code.

But internally, sorting may perform many operations.

Similarly:

ProcessStudents(students);

looks like one line.

But the function might contain:

static void ProcessStudents(string[] students)
{
    foreach (string student in students)
    {
        Console.WriteLine(student);
    }
}

Therefore:

One line of code does not mean one unit of work.

We need to understand what the code actually does.

4.16 Running Time Is Really About Growth

This is the most important idea of this article.

Suppose Algorithm A behaves like this:

10 inputs
→ about 10 operations

100 inputs
→ about 100 operations
1,000 inputs
→ about 1,000 operations

Another algorithm behaves like this:

10 inputs
→ about 100 operations

100 inputs
→ about 10,000 operations
1,000 inputs
→ about 1,000,000 operations

The important question is not:

“Which one was faster for 10 inputs?”

The more useful question is:

How quickly does the amount of work grow as n becomes larger?

That is the algorithm’s growth rate.

4.17 How to Analyze Running Time When Reading Code

When you see an algorithm, ask these questions.

1. What is the input?

Example:

an array of student scores

2. What represents the input size?

Example:

scores.Length

We usually call this: n

3. What work is repeated?

For example:

comparison
array access
loop iteration

4. What happens when n grows?

Does the algorithm perform:

roughly the same amount of work?

or:

more work?

5. How quickly does the work increase?

For example:

n
2n
n × n

This final question leads directly to Big O notation.

4.18 Running Time, Growth Rate, and Big O

These three ideas are closely connected, but they are not exactly the same.

Running Time

Running time asks:

How much work does the algorithm perform?

Growth Rate

Growth rate asks:

How does that work change as the input becomes larger?

Big O Notation

Big O gives us a simple mathematical language for describing that growth.

The learning path is:

Algorithm
   ↓
Amount of Work
   ↓
Input Gets Larger
   ↓
Observe the Growth
   ↓
Describe the Growth with Big O

4.19 Important Terms

Algorithm

A sequence of steps used to solve a problem.

Input

The data given to an algorithm.

Input Size

The amount of input data.

Usually represented by:

n

Operation

A piece of work performed by an algorithm.

Examples:

comparison
addition
array access
loop iteration

Running Time

The amount of work performed by an algorithm.

Growth Rate

How quickly the amount of work changes as the input grows.

Scalability

How well an algorithm or system handles increasing amounts of data.