Asymptotics Notes
Author: Kelly Lin

A. Best and Worse Case

It is important to remember that with asymptotics, we will only consider the runtime for cases where the value or size of the input becomes very large (e.g. as the length of an array approaches infinity). This means that we cannot derive a best or worst case runtime from a scenario where our input is small (e.g. N = 1 or some other small value, or the length of the array is 1).

Consider the following method:

public static int foo(int N) {
    if (N == 1) { return 1; }
    else { /* More code here... */ }
}

It would be incorrect to say "the best case runtime occurs when N = 1, resulting in a best case runtime of ϴ(1)". To find the best and worst case runtimes of a function, we should only be considering very large inputs that might cause the runtime to change.

When describing a best or worst case runtime, we want to provide a tight bound using ϴ(·) notation whenever possible to be as precise as possible. In the situation where the function we are analyzing has different asymptotic runtimes depending on the configuration of the inputs, we will often provide two bounds (best case and worst case) to allow us to keep providing precise runtimes.

Consider the following method:

public static void bar(int N) {
    if (N % 2 == 0) { /* Runs in log(N) time. */ }
    else { /* Runs in N! (N factorial) time. */ }
}

Although it would be true to state that bar runs in O(N!) time, we can be more specific! In order to provide a more precise runtime and use ϴ(·) notation, we can provide two runtimes: a best case and worst case runtime. It would be more precise to say that in the best case bar runs in ϴ(logN) time, and in the worst case it runs in ϴ(N!) time.

B. Some Important Sums

There are several classes of sums that appear fairly often in runtime problems. The following sections briefly explain how they can be derived.

Sum of an Arithmetic Sequence

The general solution to determine the sum of an arithmetic sequence (the sum of the first consecutive N natural numbers) can be interpreted as the average of the first and last elements, multiplied by the total number of elements:

arithmetic series

Sum of a Geometric Sequence

To determine the sum of the first N terms of a geometric series we can use the following formula ($a$ is the first term of the series, r is the common ratio):

geometric series

Here's an example of how we can apply this formula to determine the runtime of a function:

public static void honk(int N) {
    for (int i = 0; i <= N; i *= 2) {    // This is the outer loop.
        for (int j = 0; j < i; j += 1) { // This is the inner loop.
            System.out.println("HONK");  // Printing takes constant time.
        }
    }
}

The inner for loop runs a total of i times and does a constant amount of work for each iteration. Each time the inner for loop runs, its runtime is (total number of iterations) · (work per iteration) = i · 1 = i. The outer for loop runs a total of logN iterations and does i work for each iteration. To get the total runtime of honk, we sum up the work done for each iteration of the outer loop:

honk runtime equation

In our runtime analysis of honk, our ratio was 2 and our last term was N. If we solve for the generic case where the ratio is r and the last term is some function of N, f(N), we will eventually get the following result:

geometric_function_generalization

This is a powerful and general result that means that for any geometric series we see in a runtime problem, the runtime will run with respect to whatever the last term is.

C. Recursive Runtime Tips

A helpful way to analyze the runtime of a recursive function is to consider a tree which represents all of the function calls. In doing this you might want to determine the following:

total work equation