Small Steps III — Thinking with Programs

How many times can a range be halved?

Understand how often a range can 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

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

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

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.

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

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

    print(steps);
}