Small Steps III — Thinking with Programs

How Much Work Does a Program Do? (Optional)

How Much Work Does a Program Do? (Optional)

Explore one topic in small steps. Try the examples one at a time and take a break whenever you need. Choose how many extra exercises you want to try.

How much work does more data require?

What you will learn

Time complexity describes how the amount of required work grows as the number of data items increases. It is different from actual seconds.

Try it

Example · example1.cpp
void small_main()
{
    Array<int> sizes = {10, 100, 1000};

    for (int i = 0; i < sizes.length(); i = i + 1)
    {
        int n = sizes[i];
        int linear = n;
        print("n = ", n, ", linear worst case = ", linear);
    }
}

When a linear search fails, it checks all n elements. With n equal to 10, 100, and 1000, the worst-case comparison counts are also 10, 100, and 1000.

This growth is written O(n). Rather than measuring time, the example displays the amount of work numerically.

How many times can a range be halved?

What you will learn

Halving a range each time makes the iteration count grow slowly even as the data grows. This growth is called O(log n).

Try it

Example · complexity_2_example2.cpp
void small_main()
{
    int n = 1024;
    int steps = 0;

    while (n > 0)
    {
        print(n);
        n = n / 2;
        steps = steps + 1;
    }

    print("Steps: ", steps);
}

Repeatedly halve 1024 using integer division. Processing 1024, 512, …, 1 produces Steps: 11.

This is the example's iteration count, not the exact comparison count of every binary search. Big-O summarizes a growth trend.

Exercise

Imagine a Linear Search for an absent value among 20 values. Count and print the actual comparisons.

Exercise starter · exercise1_starter.cpp
void small_main()
{
    Array<int> numbers(20);
    int comparisons = 0;

    // Search for 99 and count comparisons.

    print(comparisons);
}

Hint

Increase comparisons for each value inspected and make the search reach the end without a match.

show solution
void small_main()
{
    Array<int> numbers(20);
    int comparisons = 0;

    for (int i = 0; i < numbers.length(); i = i + 1)
    {
        comparisons = comparisons + 1;
        if (numbers[i] == 99)
            break;
    }

    print(comparisons);
}
Try More (Optional)

Exercise

Start at n=1000 and keep dividing by 2 until n becomes 0. Count the steps required.

Exercise starter · complexity_2_exercise2_starter.cpp
void small_main()
{
    int n = 1000;
    int steps = 0;

    // Keep dividing by 2.

    print(steps);
}

Hint

In while, divide with n = n / 2 and increase count.

show solution
void small_main()
{
    int n = 1000;
    int steps = 0;

    while (n > 0)
    {
        n = n / 2;
        steps = steps + 1;
    }

    print(steps);
}
← Previous lessonNext lesson →