Skeleton 1. worstTime(n) is O(1):
S
For example, for the following constructor from Chapter 1, worstTime(n) is O(1):
public HourlyEmployee (String name, int hoursWorked, double payRate)
{
this.name = name;
this.hoursWorked = hoursWorked;
this.payRate = payRate;
if (hoursWorked <= MAX_REGULAR_HOURS)
{
regularPay = hoursWorked * payRate;
overtimePay = 0.00;
} // if
else
{
regularPay = MAX_REGULAR_HOURS * payRate;
overtimePay = (hoursWorked - MAX_REGULAR_HOURS) * (payRate * 1.5);
} // else
grossPay = regularPay + overtimePay;
} // 3-parameter constructor
Because n is not specified or implied, the number of statements executed is constant—no
matter what n is—so worstTime(n) is O(1). It follows that for the following method in the
HourlyCompany class, worstTime(n) is also O(1):
protected FullTimeEmployee getNextEmployee (Scanner sc)
{
String name = sc.next();
int hoursWorked = sc.nextInt();
double payRate = sc.nextDouble();
return new HourlyEmployee (name, hoursWorked, payRate);
} // method getNextEmployee
Note that the execution of S may entail the execution of millions of statements. For example:
double sum = 0;
for (int i = 0; i < 10000000; i++)
sum += Math.sqrt (i);
The reason that worstTime(n) is O(1) is that the number of loop iterations is constant and
therefore independent of n. In fact, n does not even appear in the code. In any subsequent
analysis of a method, n will be given explicitly or will be clear from the context, so you
needn’t worry about “What is n?”
Skeleton 2. worstTime(n) is O(log n):
while (n > 1)
{
n = n / 2;
S
} // while
Let t (n) be the number of times that S is executed during the execution of the while
statement. Then t (n) is equal to the number of times that n can be divided by 2 until
n equals 1. By Example A2.2 in Section A2.5 of Appendix 2, t (n) is the largest integer
≤ log2 n. That is, t (n) = floor(log2 n).1 Since floor(log2 n) ≤ log2 (n) for any positive
integer n, we conclude that t (n) is O(log n) and so worstTime(n) is also O(log n).
The phenomenon of repeatedly splitting a collection in two will re-appear time and again
in the remaining chapters. Be on the lookout for the splitting: it signals that worstTime(n)
will be O(log n).
The Splitting Rule
In general, if during each loop iteration, n is divided by some constant greater than 1, worstTime(n) will be O(log n) for that loop.
As an example of the Splitting Rule, here—from the Arrays class in the package
java.util—is the most widely known algorithm in computer science: the Binary Search
Algorithm. Don’t get hung up in the details; we will study a binary search algorithm
carefully in Chapter 5. Here, n refers to the size of the array being searched.
/**
* Searches the specified array of ints for the specified value using the
* binary search algorithm. The array must be sorted (as
* by the sort method, above) prior to making this call. If it
* is not sorted, the results are undefined. If the array contains
* multiple elements with the specified value, there is no guarantee which
* one will be found.
*
* @param a the array to be searched.
* @param key the value to be searched for.
* @return index of the search key, if it is contained in the list;
* otherwise, (-(insertion point) - 1). The
* insertion point is defined as the point at which the
* key would be inserted into the array a: the index of the first
* element greater than the key, or a.length, if all
* elements in the array are less than the specified key. Note
* that this guarantees that the return value will be greater than
* or equal to 0 if and only if the key is found.
* @see #sort(int[ ])
*/
public static int binarySearch(int[ ] a, int key)
{
int low = 0;
int high = a.length-1;
while (low <= high)
{
int mid = (low + high) >> 1; // same effect as (low + high) / 2,
// but see Programming Exercise 3.5
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
} // while
return -(low + 1); // key not found.
} // method binarySearch
At the start of each loop iteration, the area searched is from index low through index high,
and the action of the loop reduces the area searched by half. In the worst case, the key is not
in the array, and the loop continues until low > high. In other words, we keep dividing
n by 2 until n = 0. (Incidentally, this repeated dividing by 2 is where the “binary” comes
from in Binary Search Algorithm.) Then, by the Splitting Rule, worstTime(n) is O(log n)
for the loop. And with just a constant number of statements outside of the loop, it is clear
that worstTime(n) is O(log n) for the entire method.
Skeleton 3. worstTime(n) is O(n):
for (int i = 0; i < n; i++)
{
S
} // for
The reason that worstTime(n) is O(n) is simply that the for loop is executed n times. It
does not matter how many statements are executed during each iteration of the for loop:
suppose the maximum is k statements, for some positive integer k. Then the total number
of statements executed is ≤ kn. Note that k must be positive because during each iteration,
i is incremented and tested against n.
As we saw in Section 3.1, worstTime(n) is O(n) for the aboveMeanCount method. But
now we can obtain that estimate simply by noting that the loop is executed n times.
public static int aboveMeanCount (double[ ] a, double mean)
{
int n = a.length,
count = 0;
for (int i = 0; i < n; i++)
if (a [i] > mean)
count++;
return count;
} // method aboveMeanCount
For another example of a method whose worstTime(n) is O(n), here is another method
from the Arrays class of the package java.util. This method performs a sequential
search of two arrays for equality; that is, the search starts at index 0 of each array, and
compares the elements at each index until either two unequal elements are found or the
end of the arrays is reached.
/**
* Returns true if the two specified arrays of longs are
* equal to one another. Two arrays are considered equal if both
* arrays contain the same number of elements, and all corresponding pairs
* of elements in the two arrays are equal. In other words, two arrays
* are equal if they contain the same elements in the same order. Also,
* two array references are considered equal if both are null.
*
* @param a one array to be tested for equality.
* @param a2 the other array to be tested for equality.
* @return true if the two arrays are equal.
*/
public static boolean equals (long[ ] a, long[ ] a2)
{
if (a==a2)
return true;
if (a==null || a2==null)
return false;
int length = a.length;
if (a2.length != length)
return false;
for (int i=0; i<length; i++)
if (a[i] != a2[i])
return false;
return true;
} // method equals
Skeleton 4. worstTime(n) is O(n log n):
int m;
for (int i = 0; i < n; i++)
{
m = n;
while (m > 1)
{
m = m / 2;
S
} // while
} // for
The for loop is executed n times. For each iteration of the for loop, the while loop
is executed floor(log2 n) times—see Example 2 above—which is ≤ log2 n. Therefore
worstTime(n) is O(n log n). We needed to include the variable m because if the inner loop
started with while (n > 1), the outer loop would have terminated after just one iteration.
In Chapter 11, we will encounter several sorting algorithms whose worstTime(n) is
O(n log n), where n is the number of items to be sorted.
Skeleton 5. worstTime(n) is O(n2):
a. f.aor (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
S
} // for j
The number of times that S is executed is n2. That is all we need to know to conclude
that worstTime(n) is O(n2). In Example 3.3, we painstakingly counted the exact number
of statements executed and came up with the same result.
b. f.bor (int i = 0; i < n; i++)
for (int k = i; k < n; k++)
{
S
} // for k
The number of times that S is executed is
n + (n − 1) + (n − 2)+· · ·+3 + 2 + 1 =
n
k=1
k
As shown in Example A2.1 of Appendix 2, the above sum is equal to
n(n + 1)/2,
which is O(n2). That is, worstTime(n) is O(n2).
The selectionSort method, developed in Chapter 11, uses the above skeleton. Here,
n refers to the size of the array to be sorted.
/**
* Sorts a specified array of int values into ascending order.
* The worstTime(n) is O(n * n).
*
* @param x – the array to be sorted.
*
*/
public static void selectionSort (int [ ] x)
{
// Make x [0 . . . i] sorted and <= x [i + 1] . . .x [x.length -1]:
for (int i = 0; i < x.length -1; i++)
{
int pos = i;
for (int j = i + 1; j < x.length; j++)
if (x [j] < x [pos])
pos = j;
int temp = x [i];
x [i] = x [pos];
x [pos] = temp;
} // for i
} // method selectionSort
There are n − 1 iterations of the outer loop; when the smallest values are at indexes x
[0], x [1], . . . x [n − 2], the largest value will automatically be at index x [n − 1]. So
the total number of inner-loop iterations is
(n − 1) + (n − 2) + . . . + 1 =
n−1
i=1
i = n(n − 1)/2
We conclude that worstTime(n) is O(n2).
c. f.cor (int i = 0; i < n; i++)
{
S
} // for i
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
S
} // for j
For the first segment, worstTime(n) is O(n), and for the second segment, worstTime(n)
is O(n2), so for both segments together, worstTime(n) is O(n + n2), which is equal to
O(n2). In general, for the sequence
A
B
if worstTime(n) is O(f ) for A and worstTime(n) is O(g) for B, then worstTime(n) is
O(f + g) for the sequence A, B.
