Lesson 2 of 4 · Algorithm complexity

Replacing Iteration with a Formula

The running time of an algorithm also depends on the way the task is solved, that is, on the number of elementary operations that have to be performed. Some problems can be solved with loops, but there is also a matching formula for them that can speed up the program considerably when the amount of input data is large.

1. Example — how far does an athlete run on the last day of training?

Athletes take part in training for a competition that lasts n days. On the first day an athlete runs a1 metres, and on every following day the athlete runs d metres more than on the previous day. Write a program that determines how many metres the athlete runs on the last day of training.

An iterative solution — with a loop

On the first day the athlete runs a1 metres. On every following day we add d to the previous value. The variable a keeps the number of metres for the current day in every step.

An example of a complete program in C:

#include <stdio.h>

int main(void)
{
    int n, a1, d, a;

    // We read the number of days, the distance on the first day and the daily increase.
    scanf("%d%d%d", &n, &a1, &d);

    // On the first day the athlete runs a1 metres.
    a = a1;

    // There are n - 1 days left, so we add d that many times.
    for (int i = 1; i < n; i++)
    {
        a = a + d;
    }

    // We print the distance run on the last day.
    printf("%d\n", a);

    return 0;
}

For example, if n = 5, a1 = 3 and d = 2, the distances by days are:

3, 5, 7, 9, 11

On the last, fifth day, the athlete runs 11 metres. The loop runs n - 1 times, because the initial value a1 is already the distance for the first day.

A solution with a formula

The numbers that the athlete runs by days form an arithmetic sequence. The first term of that sequence is a1, and the difference between neighbouring terms is d.

The n-th term of an arithmetic sequence is calculated with the formula:

a_n = a_1 + (n - 1) · d

For our example we get:

a_5 = 3 + (5 - 1) · 2 = 3 + 8 = 11

That is why, instead of a loop, we can calculate the answer directly with the formula. The program is shorter, and the number of arithmetic operations does not depend on the number of days.

The solution in C:

#include <stdio.h>

int main(void)
{
    int n, a1, d, an;

    // We read the number of days, the distance on the first day and the daily increase.
    scanf("%d%d%d", &n, &a1, &d);

    // We calculate the n-th term of the arithmetic sequence directly.
    an = a1 + (n - 1) * d;

    // We print the distance run on the last day.
    printf("%d\n", an);

    return 0;
}

If the total distance that the athlete ran during all the days also has to be calculated, the formula for the sum of the first n terms of an arithmetic sequence is used:

S_n = n · (a_1 + a_n) / 2

It is important to tell these two questions apart: the formula for a_n determines how far the athlete ran on the last day, while the formula for S_n determines how far the athlete ran in total during all the days.

2. Formulas from combinatorics

In some tasks the number of possibilities can be calculated with a formula, without listing all the possibilities with loops. Variations, permutations and combinations without repetition are often used.

Kind Formula Meaning
Variations without repetition V(n, k) = n · (n - 1) · ... · (n - k + 1) = n! / (n - k)! k elements out of n in total are chosen and arranged; the order matters.
Permutations P(n) = n! = n · (n - 1) · ... · 1 All the elements are arranged; the order matters.
Combinations without repetition C(n, k) = n! / (k! · (n - k)!) k elements out of n in total are chosen; the order does not matter.

Combinations without repetition can also be written like this:

C(n, k) = [n · (n - 1) · ... · (n - k + 1)] / k!

The denominator is k!, not n!. This form is useful when we need to calculate the number of ways to choose k elements out of n elements in total.

3. Example — the number of segments in a binary string

A binary string is given, that is, a string that consists only of the characters 0 and 1. Determine the number of segments of length at least 2 that start and end with the character 1. A segment must be a part of the string with consecutive characters.

Let us look at the string:

s = "010010001"

In this string the ones are at the positions 2, 5 and 9, if we count the positions from 1. Every pair of different ones determines exactly one segment that starts and ends with a one. The segments we are looking for are:

0[1001]0001
0100[10001]
0[10010001]

There are 3 ones in the string. We choose two of them: one that will be the start of the segment and another that will be the end. That is why the number of segments equals the number of combinations of 3 elements taken 2 at a time:

C(3, 2) = 3! / (2! · (3 - 2)!) = (3 · 2) / (2 · 1) = 3

This conclusion also holds for strings of other lengths: if the string contains b ones, every choice of two different ones determines one segment. That is why the total number of segments is:

number_of_segments = b · (b - 1) / 2

A solution with the formula — C

First we go through the entered string and count how many ones it has. Then we apply the formula b · (b - 1) / 2. The following program reads characters up to the end of the line or the end of the input.

#include <stdio.h>

int main(void)
{
    int ones = 0;
    int ch;
    long long segments;

    // We read characters up to the end of the line or the end of the input.
    while ((ch = getchar()) != EOF && ch != '\n')
    {
        // We count the ones in the string.
        if (ch == '1')
        {
            ones++;
        }
    }

    // Every pair of ones determines one segment we are looking for.
    segments = (long long)ones * (ones - 1) / 2;

    printf("%lld\n", segments);

    return 0;
}

A solution with the formula — C++

In C++ we can read the whole string into a variable of type string and go through it with a for loop. Here too we count the ones, and then calculate the number of segments directly with the formula.

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    long long ones = 0;
    long long segments;

    // We read the binary string.
    cin >> s;

    // We count how many ones the string contains.
    for (char c : s)
    {
        if (c == '1')
        {
            ones++;
        }
    }

    // The number of segments equals the number of pairs of ones.
    segments = ones * (ones - 1) / 2;

    cout << segments << endl;

    return 0;
}

Explaining the solution

After counting the ones we have the value b. We do not have to find and print every segment separately. It is enough to calculate how many different pairs of ones there are.

For the example 010010001 we get:

b = 3
number_of_segments = 3 · (3 - 1) / 2 = 3

Both versions that use the formula have the time complexity O(n), because we go through the string once to count the ones. The extra space taken by the counting variables is constant, not counting the memory needed for the string itself in the C++ version.

Another variant — counting with two loops

The task can also be solved by looking, for every one, for all the ones that come after it. Every pair found is one segment. This solution is easier to understand when you are just learning to work with loops, but it is slower for long strings.

#include <stdio.h>
#include <string.h>

int main(void)
{
    char s[100002];
    size_t n;
    long long segments = 0;

    // We read the string; fgets is a safer replacement for gets.
    if (fgets(s, sizeof(s), stdin) == NULL)
    {
        return 0;
    }

    // We determine the length of the string, without the newline character.
    n = strcspn(s, "\r\n");

    // We choose the first one of the segment.
    for (size_t i = 0; i < n; i++)
    {
        if (s[i] == '1')
        {
            // We look for all the ones that come after it.
            for (size_t j = i + 1; j < n; j++)
            {
                if (s[j] == '1')
                {
                    segments++;
                }
            }
        }
    }

    printf("%lld\n", segments);

    return 0;
}

Comparing the approaches

Approach Time complexity Explanation
Counting the ones and a formula O(n) One pass through the string, and then a constant number of arithmetic operations.
Two nested loops O(n²) For every one, all the characters after it are checked.

Conclusion: when we can recognise a mathematical formula that matches the task, we can often avoid a large number of repeated operations. In this example the formula reduces the complexity from O(n²) to O(n).


Check your knowledge

Open the quiz

Replacing iteration with a formula

1. What is the n-th term of an arithmetic sequence with the first term a₁ and the difference d?




2. A string has b ones. How many segments start and end with a one?




3. What is the complexity of the solution that counts the ones and uses a formula?