Navigation
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:
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):
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:
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:
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:
- Determine the height of the tree. There are various ways in which to do this which will be shown in discussions.
- Determine the branching factor. This is typically the number of recursive function calls that are made from each call of the function. You can also use the branching factor in determining the number of nodes at any given layer of the tree.
- Determine the amount of work done at each node relative to the input size. We should be careful here as this may or may not be the same amount of work being done at every node in a given level of the tree.
- Calculate the entire amount of work being done in the entire function call by using the following equation: