Small Steps III — Thinking with Programs

How much work does more data require?

Understand how the amount of work grows with more data.

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

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.

Exercise

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

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.

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);
}