Algorithmic Analysis
— print (last updated: Sep 14, 2009) — print

Select font size:
Algorithmic Analysis is usually about the "speed" of an algorithm. How do we measure speed? By abstract time we mean that we decide on some programming event to count regardless of what constitutes this event while ignoring various details.

The other issue when measuring speed is that the speed may depend on the input in which case there are possibly three things of interest to us: The best case is generally not of interest; its primary value is to ascertain the minimum amount of work an algorithm must do regardless of its input.

The worst case is often the thing we analyze first, because it represents an upper bound on the time. This, however, is not the complete story, because it represents the behavior of a single operation. In some cases, an operation repeated multiple times will have a better worst-case behavior than any single operation. Such worst-case analysis is referred to as the amortized worst-case behavior.

The average case is often a good judge of what to expect in a "generic" situation. This analysis is usually the most challenging and often summons deep layers of mathematics to study it. The other issue with averaging is how to characterize a generic situation. Usually the assumption is that event are "equally likely", but that is often not the case. For example in a text search, say, to count the occurrences of certain words, one typically takes advantage of the well-known fact that certain words occur much more frequently than others.

Testing the sample programs

The algorithms in this document can be run and tested individually in NetBeans. Instead of creating a project for each, create a new project, Miscell. We do not particularly need the auto-created Main class, so delete it if you'd like.

For each of the sample programs do the following:
  1. From the Projects window, right-click either on
  2. Select New Other and from the list select Java Main Class (only need to go throuh Other once).
  3. In the popup window (Name and Location), set the Class Name something related to the algoritm of interest, like LinearSearch for the linear search algorithm. You want these entries set: 
    Class Name: LinearSearch
package:    miscell
  4. In some situations you'll want to create a simple Java Class, not Java Main Class.
  5. Replace the class content by the suggested content.
  6. In every case you will need the import line: 
    import java.util.*;
  7. Run the program by locating it in Source Packages miscell, right-clicking and selecting Run File.
  8. To make repeated runs easier, select Customize in the drop-down below <default config>. In this window, use the Browse button to specify the Main Class.

Linear Search

For example, consider simple linear search of an integer array for a given key value. A simple "random" linear search might be something like this: 
package miscell;

import java.util.*;

public class LinearSearch1 {

  public static void main(String[] args) {
    Random rand = new Random();

    int size = 20;

    int A[] = new int[size], key;

    for (int i = 0; i < A.length; ++i) {
      A[i] = rand.nextInt(size * 2);
    }

    key = rand.nextInt(size * 2);

    System.out.println("A = " + Arrays.toString(A));
    System.out.println("key = " + key);

    int i;
    for (i = 0; i < A.length; ++i) {
      if (key == A[i]) {
        break;
      }
    }
    boolean found = (i != A.length);

    System.out.println("found = " + found);
    System.out.println("comparisons: " + (found ? i + 1 : size));
  }
}

Coding

In order to create a "general" version which could be reused, we should consult what Java does in the Arrays class. There is no linear search algorithm, but there is a binary search. Here are two relevant static functions: 
int binarySearch(int[] a, int key)
int binarySearch(int[] a, int fromIndex, int toIndex, int key)
The "toIndex" argument name is misleading since the range is really between fromIndex and toIndex – 1, inclusive. Thus these two calls are equivalent: 
java.util.Arrays.binarySearch(A, key);
java.util.Arrays.binarySearch(A, 0, A.length, key);
The int return value is supposed to be the position at which the key is found. If not found, a negative value is returned.

These algorithm specifications suggest a more general way to write linear search, namely using our own package, util, and our own class MyArrays with two versions: 
util.MyArrays.linearSearch(int[] a, int key)
util.MyArrays.linearSearch(int[] a, int fromIndex, int toIndex, int key)
We should also consider what to do if the latter of these calls is provided with invalid arguments such as these: 
linearSearch(A, -3, 2, 15);
linearSearch(A, 3, 2, 15);
In these cases, we want to throw an Exception. A few tests of Arrays.binarySearch leads us to add this starter code: 
    if (fromIndex < 0 || toIndex < 0 || fromIndex > toIndex) {
      throw new IllegalArgumentException();
    }
In Netbeans, create the Java Class: 
Class Name  MyArrays
package     util
with this content: 





util.MyArrays




package util;

public class MyArrays {

  public static int linearSearch(int[] A, int fromIndex, int toIndex, int key) {
    if (fromIndex < 0 || toIndex < 0 || fromIndex > toIndex) {
      throw new IllegalArgumentException();
    }

    int i;
    for (i = fromIndex; i < toIndex; ++i) {
      if (key == A[i]) {
        return i;
      }
    }
    return -1;
  }

  public static int linearSearch(int[] A, int key) {
    return linearSearch(A, 0, A.length, key);
  }
}
Apply this search algorithm by creating the following Main Class with this content: 
package miscell;

import java.util.*;
import util.MyArrays;

public class LinearSearch2 {

  public static void main(String[] args) {

    Random rand = new Random();

    int size = 20;

    int A[] = new int[size], key;

    for (int i = 0; i < A.length; ++i) {
      A[i] = rand.nextInt(size * 2);
    }
    key = rand.nextInt(size * 2);

    System.out.println( "A = " + Arrays.toString(A) );
    System.out.println( "key = " + key );

    int pos = MyArrays.linearSearch(A, key);
    System.out.println(
      "\n" +
      "linear search" + "\n" +
      "return = " + pos + "\n" +
      "comparisons: " + (pos >= 0 ? pos+1 : size )
    );
  }
}

Other Java types

Consider expanding the linear search algorithm to other types such as float or String. These two are very different because float, like int is a primitive type and String is an Object. With respect to float, or any of the other primitive types, we have to write separate functions for each even though they effectively do the same thing.

Regarding String or other Object types, we would want a generic version which would be expressed like this: 
  public static <T> int linearSearch(T[] A, int fromIndex, int toIndex, T key) {
    if (fromIndex < 0 || toIndex < 0 || fromIndex > toIndex) {
      throw new IllegalArgumentException();
    }

    int i;
    for (i = fromIndex; i < toIndex; ++i) {
      if (key.equals(A[i])) {
        return i;
      }
    }
    return -1;
  }

  public static <T> int linearSearch(T[] A, T key) {
    return linearSearch(A, 0, A.length, key);
  }

Abstract time for linear search

Regarding the notion of "abstract time" we usually say to "count the number of comparisons" to get a measure of the actual time. There are several deviations from reality: Nevertheless, simplifications such as this is useful for algorithm analysis is worthwhile because we can more easily go on and describe the behavior of arbitrarily large arrays.

Language of Asymptotics

Asymptotics has to do with describing run-time behavior of algorithms for arbitrarily large problem sizes. Often a problem size can be characterized by a single parameter n, e.g., search an array of size n, sort an array of size n.

Consider the worst-case time for linear search on an array of size n. Clearly the worst case is that we have to go all the way through the array successful or not. Let T(n) be this time, then 
T(n) ≤ D1 + D * n
where D1 represent the initializations and the D factor counts the comparison plus all the variable manipulations.

Big-O Notation

We would really like to present information about this algorithm which ignores the constants. The "big O" notation and "complexity terminology" lets us do precisely that. We say: 
T(n) = O(f(n))   or   T(n) is in O(f(n))
if there are constants C and k, such that 
T(n) ≤ C * f(n),  for all n ≥ k
The idea of "n ≥ k" means eventually it has this behavior if we ignore some initial finite portion. For example, suppose 
T(n) = 100 + n
This indicates that there is some fixed initial cost regardless of the problem size. We can say: 
T(n) ≤ 101 * n, for all n ≥ 1
but we can also say 
T(n) ≤ 2 * n, for all n ≥ 100
getting a "better" asymptotic constant, C, in the sense that it is smaller (we can always make it larger). Going back to our worst-case for linear search, write: 
T(n) ≤ D1 + D * n = (D + D1/n) * n
If n ≥ D1, then T(n) ≤ (D+1) * n, and so T(n) = O(n), using the the "C" constant C = D+1.

Analysis of Linear Search

The worst case is if the element is not found or is found at the end of the search in which case there are n comparisons. The best case is that the thing you're looking for is in the first slot and so there's only one comparison. We say:
the worst case is O(n); the best case is O(1)

Average case for linear search

A simple idea is to take the average of the best and worst. This would be (n+1)/2, which turns out to be "correct". However, we must make an additional assumption that the search will be successful. Why? Consider an array of size 10, holding arbitrary integers and the key is an arbitrary integer. Given that there are about 4 billion 32-bit integers, the chance that our key is one of these 10 is almost zero!

So we assume that it is equally likely to find the key in each of the n positions. Using this notion, the average cost is: 
(total cost for all n position) / n
The cost for finding in position i is (i+1), i = 0…n-1;, so we get 
1/n * ∑i = 0,…,n-1(i+1) = 1/n * ∑i = 1,…,ni = 1/n * (n*(n+1))/2 = (n+1)/2

Logarithms in analysis

Logarithms, particularly base-2 logarithms are important because they represent the number of times n things can be halved. 
n, n/2, n/4, ..., 1
How many terms in this sequence? Roughly, 
log2n
It comes from the definition of logarithm to the base b: 
logbn = x    means   bx = n, i.e., blogbn = n
All bases differ only by a constant: 
blogb2 = 2
(blogb2)x = blogb2*x = 2x
blogb2*log2n = 2log2n = n
so 
logbn = logb2*log2n
Common bases: For scientific computations, log(n) is understood to be the base-10 logarithm and ln(n) the natural logarithm. In computer language library functions, log(n) can mean the natural logarithm and base-2 logarithm is usually written with an explicit base. For our purposes, since the base-2 is preeminent, we'll drop the 2 and assume: 
log n = log2n
As far as order measures are concerned, all bases are equal.

Binary Search

Binary search searches a sorted array in an efficient way in the most efficient way possible. This is a simple example of a divide-and-conquer strategy in which we subdivide the problem into equal-sized "sub-problems". The idea is simple: compare the key to the "middle" element, if not equal, either look left or look right portion based on whether the key is less than, or greater than, the middle element.

This algorithm expresses itself most naturally in a recursive manner based on the way I say:
search the whole leads to search one half or another.
In order to express the recursive nature, the parameter of the algorithm must allow arbitrary beginnings and ends. Our inital coding might look something like this: 
int binarySearch(int[] A, int fromIndex, int toIndex, int key) {
    if (fromIndex == toIndex) { 
      return - 1; 
    }

    int mid = (fromIndex + toIndex) / 2;
    if (key == A[mid]) {
      return mid;
    }
    // else
    if (key < A[mid]) {
      return binarySearch(A, fromIndex, mid, key);
    }
    // else // key >  A[mid]
    return binarySearch(A, mid+1, toIndex, key);
}
The else keywords are optional because of the return statements. One has to keep in mind that the division used to compute mid is integer division (i.e., truncation). As is the case with linearSearch, the toIndex parameter is off the right edge of the array. Our textbook makes, in my opinion, the unfortunate decision to make the second parameter position in his array-based algorithms the rightmost index, so beware.

Binary Search Analysis

The idea behind binary search is simple, but you need to make a proof of the algorithm to make sure the details are correct.

Correctness proof

The algorithm's correctness statement is this:
The execution of 
int pos = binarySearch(A, fromIndex, toIndex, key)
sets pos ≥ 0 if and only if key is present in A at position pos, where 
fromIndex ≤ pos < toIndex
Actually we should say something about what pos means when it is a negative value on a failed search, but this is sufficient for now.

The proof is by induction on the array size, len = toIndex - fromIndex. It is a good idea to run a few examples by hand. Again, keep in mind that computer integer division is trunctated. In mathematical terms, division of two integers with integer result: 
a/b
is expressed using the "floor" function flr, which simply truncates any decimal part.
flr(a/b)
For simplicity, we will not worry too much about the distinction.
Base case: len = 0
This means that toIndex == fromIndex. The key cannot be present in the array and the algorithm indicates failure.
Case: len > 1
Thus, toIndex = fromIndex + 1 and we compute: 
mid = (fromIndex + toIndex)/2 = (2*fromIndex + 1)/2 = fromIndex
we see if the key is at fromIndex and then either
Inductive case: len > 0
Because the array is sorted, it is obvious that the algorithm will work so long as: The even and odd cases values need to be considered separately. This analysis below shows that
  1. len > 0 is even
    Write len = 2*k where k &ge 1. Then toIndex = fromIndex + 2*k. Compute: 
    mid = (fromIndex + toIndex)/2 = (2*fromIndex + 2*k)/2 = fromIndex + k
    and thus, 
    fromIndex < mid = fromIndex + k < fromIndex + 2*k = toIndex
    The left-hand side has this many elements: 
    mid - fromIndex = k
    and the right-hand side has this many elements: 
    toIndex - (mid+1) = fromIndex + 2*k - (fromIndex + k + 1) = k - 1
    Since k ≥ 1, in both cases the values are less than len = 2 * k.
  2. len > 0 is odd
    Write len = 2*k + 1 where k &ge 0. Then toIndex = fromIndex + 2*k + 1. Compute: 
    mid = (fromIndex + toIndex)/2 = (2*fromIndex + 2*k + 1)/2 = fromIndex + k
    and thus, 
    fromIndex ≤ mid = fromIndex + k < fromIndex + 2*k + 1 = toIndex
    The left-hand side has this many elements: 
    mid - fromIndex = k
    and the right-hand side has this many elements: 
    toIndex - (mid+1) = fromIndex + 2*k + 1 - (fromIndex + k + 1) = k
    Both sides have k elements which is less than len = 2 * k + 1.

Worst-case timing Analysis

From an analysis perspective, with an array of size n > 1, 
n even => left side n/2, right side n/2 - 1 
n odd  => both sides have size (n-1)/2 = n/2
Let
T(n) = worst case number of comparisons in binary search with an array of size n
In the worst case, we would end up exploring a side with n/2 elements: 
T(1) = 1
T(n) = 1 + T( n/2 ), n > 1
Look at some computed values 
T(2) = 2
T(3) = 2
T(4) = 3
T(5) = 3
Claim: 
T(n) ≤ 1 + log n
Proof by induction.
Verify for n = 1. Assume valid up to (but not including) some n ≥ 2. Prove for n: 
T(n) = 1 + T(n/2) 
     ≤ 1 + 1 + log( n/2 )   (induction, since flr(n/2) < n)
     = 1 + 1 + (log(n) - 1)   (property of log)
     = 1 + log(n)                (simple algebra)
And so, since we can effectively ignore the "1", we say:
The average time for binary search is O(log n)

Average-case timing Analysis

The average case timing is more complicated. As in the case of linear search, we assume a successful search, and the each of the positions are equally likely. Lay out the positions that the algorithm would visit in a tree, where the root is the middle of the array, the left and right subtrees are generated by searches of the left and right subarrays, respectively. Here are the layouts for array sizes 3 and 7:
       
The level of a node is its distance from the root. The root, at level 0, counts for 1 comparison. Both of its children count for 2 comparisons each. In general, at level i there will be 2i children, each counting for (i+1) comparisons.

In general the tree will not be perfect, but it can be shown that Thus, using the expression (counting levels 0 to h-1): 
Count(h) = ∑i = 0,…,h-1 2i* (i+1)
we can derive this relation for the averge time, T(n): 
1/n * Count( flr(log n) )  ≤  T(n)  ≤  1/n * Count( 1 + flr(log n) )
The value of Count(h) is a well-known series sum: 
Count(h) = (h — 1) * 2h + 1
Thus, in particular, using the left-hand side of the above inequality, we can determine that: 
T(n) ≥ 1/n * ( flr(log n) — 1 ) * 2flr(log n) + 1
Using the fact that flr(log n) > log(n) — 1, a substitution gives: 
T(n) ≥ 1/n * (log(n) — 2) * 2(log(n)—1) 
     = 1/n * (log(n) — 2) * ½ n
     = ½ log(n) — 1
Thus the average time is still logarithmic with multiplicative constant somewhere between ½ seen here and the worst case, 1, computed above.

Binary Search Code

Java Collection version

We first want to see what happens with Java's Arrays.binarySearch algorithm to get an idea of how to write the algorithm. Create the BinarySearch Main Class and test run: 
package miscell;

import java.util.*;
//import util.MyArrays;

public class BinarySearch {

  public static void main(String[] args) {

    Random rand = new Random();

    int size = 20;

    int A[] = new int[size], key;

    for (int i = 0; i < A.length; ++i) {
      A[i] = rand.nextInt(size * 2);
    }
    key = rand.nextInt(size * 2);

    /*
    for (int i = 0; i < A.length; ++i) {
      A[i] = i+1;
    }
    key = 0;
    key = 21;
    */

    System.out.println("A (initial) = " + Arrays.toString(A));
    Arrays.sort(A);
    System.out.println("A (sorted)  = " + Arrays.toString(A));
    System.out.println("key = " + key);

    int pos;

    pos = Arrays.binarySearch(A, key);
    System.out.println(
      "\n" +
      "binary search from Arrays class" + "\n" +
      "return = " + pos + "\n" +
      "found = " + (pos >= 0) + "\n"
      );
  }
}

Our own version

Our version is created by adding code to the util.MyArrays class. Here is the code 





util.MyArrays — code added




  private static int count;

  public static int getCount() { return count; }

  public static void setCount(int count) { MyArrays.count = count; }

  public static int binarySearch(int[] A, int fromIndex, int toIndex, int key) {
    if (fromIndex == toIndex) {
      return - fromIndex - 1;
    }

    ++count;
    int mid = (fromIndex + toIndex) / 2;
    if (key == A[mid]) {
      return mid;
    }
    if (key < A[mid]) {
      return binarySearch(A, fromIndex, mid, key);
    }
    // else key > A[mid]
    return binarySearch(A, mid+1, toIndex, key);
  }

  public static int binarySearch(int[] A, int key) {
    return binarySearch(A, 0, A.length, key);
  }

Failed search value

We have modified the return value in case of failure. Before we wrote simply 
return -1;
However, we can provide better information which indicates the position that the key should be added. This is done by: 
return  - fromIndex - 1;
We are insured that this is negative under all circumstances. Here's how we can use it:
When the key is not found the return value, ret < 0. Compute the insert position as: 
int insert_pos = - ret + 1;
Then if we the new array will contain key and be sorted.
It's good to verify this with an example. Suppose the array is
010203040
01234
Here are two cases:

Counting comparisons

The other feature introduced is that of counting the number of comparisons. Unlike linear search, the position at which an element is found is not easily related to the number of comparisons made to find the key value at that position. In order to simplify this accounting, a special static counting variable is introduced from the class framework. It can be controlled externally via the standard get/set member functions used before and after the function call.

Error Checking

We've left out the error checking line: 
  public static int binarySearch(int[] A, int fromIndex, int toIndex, int key) {
    if (fromIndex < 0 || toIndex < 0 || fromIndex > toIndex) {
      throw new IllegalArgumentException();
    }
The reason is that in the recursive call stack which happens, only the first call needs to check for invalid arguments; the other calls will never have this issue. If we wanted to really be super-efficient, a better approach would be to have the public binarySearch function call a private recursive function like this: 
  public static int binarySearch(int[] A, int fromIndex, int toIndex, int key) {
    if (fromIndex < 0 || toIndex < 0 || fromIndex > toIndex) {
      throw new IllegalArgumentException();
    }
    rec_binSearch(A, fromIndex, toIndex, key);
  }

  private static int rec_binarySearch(int[] A, int fromIndex, int toIndex, int key) {
    if (fromIndex == toIndex) { return - fromIndex - 1; }

    ++count;
    int mid = (fromIndex + toIndex) / 2;
    if (key == A[mid]) {
      return mid;
    }
    if (key < A[mid]) {
      return rec_binarySearch(A, fromIndex, mid, key);
    }
    // else key > A[mid]
    return rec_binarySearch(A, mid+1, toIndex, key);
  }
Although this approach is probably overkill, the separation of the public interface function calling a private recursive helper is quite common in practice.

Testing

To test out this user-created version, add the following code to the end of the main function in the BinarySearch class: 
    MyArrays.setCount(0);
    pos = MyArrays.binarySearch(A, key);
    System.out.println(
      "\n" +
      "binary search from MyArrays class" + "\n" +
      "return = " + pos + "\n" +
      "comparisons: " + MyArrays.getCount()
      );

Other types

The situation is similar, but more complicated than that of linear search for generic types. The code we want is: 
  public static <T> int binarySearch(T[] A, int fromIndex, int toIndex, T key) {
    if (fromIndex == toIndex) {
      return - fromIndex - 1;
    }

    ++count;
    int mid = (fromIndex + toIndex) / 2;

    int comp = ((Comparable) key).compareTo(A[mid]);
    if (comp == 0) {
      return mid;
    }
    if (comp < 0) {
      return binarySearch(A, fromIndex, mid, key);
    }
    // else comp > 0
    return binarySearch(A, mid+1, toIndex, key);
  }

  public static <T> int binarySearch(T[] A, T key) {
    return binarySearch(A, 0, A.length, key);
  }
In particular, we must drop the normal inequality comparison operations in preference of the compareTo member function. Unlike the equals function which is defined at the Object level, the compareTo function is only defined for Comparable objects. Thus we assume the array element type, T, is Comparable by forcing a cast, getting this code: 
    int comp = ((Comparable) key).compareTo( A[mid] );
The value of comp determines one of the three relations:
less than if comp < 0,
equals if comp == 0,
greater than if comp > 0.
Note that, in reality, there are one or two actual comparisons, but we ignore that and declare this as one comparison.

Binary vs. Linear search

The problem with binary search is that, although the search time is much faster, the setup time is significant, namely, the array must be sorted. The best algorithms for sorting a "random" array cost O(n * log n). So there is no advantage over linear search if every search requires a sort.

Here is how binary search gains:
  1. The array is sorted once and then repeatedly searched. If there are O(n) searches then the average time for linear search would be O(n2) whereas for binary search, O(n * log n).
  2. The array is modified by adding new elements, one at a time between (multiple) successive searches. The issue here is that the time to add an element to an unsorted array is considered to be O(1), whereas adding to a sorted array requires finding the right insert position (O(log n)) and then shifting the array to create an available slot (O(n)).

The n*log n recurrence relation

The textbook indicates the following recurrence relation on page 41: 
T(1) = 1
T(n) = 2 * T(n/2) + O(n),  n > 1
We want to solve this relation since this is a very common one in practice for divide-and-conquer algorithms: First of all, let's understand the O(n) term. It means that: 
T(n) = 2 * T(n/2) + f(n)
where there exist constants C1 and k such that: 
f(n) ≤ C1 * n, for all n ≥ k
It is relatively easy to argue that there is a possibly larger constant, C, such that: 
f(n) ≤ C * n, for all n ≥ 1
Simply choose C ≥ C1 so that this inequality holds for the (finite) list of values n = 1,…,k-1.

So we can now write: 
T(1) = 1
T(n) ≤ 2 * T(n/2) + C*n,  n > 1
Let's compare T(n) and n * log n for the first few values of n > 1
T(n) n * log n 
T(2) ≤ 2*T(1) + C = 2+C*2                = (C+1) * 2
T(3) ≤ 2*T(1) + C*3 = 2+3*C              < (C+1) * 3
T(4) ≤ 2*T(2) + C*4 = 2*(2*(C+1)) + C*4  < (C+1) * 8

2 = 2 * log 2
3 < 3 * log 3
8 = 4 * log 4
A likely order constant for T(n) = O(n * log n) is C+1, i.e., 
T(n) ≤ (C+1) * n * log n,   n > 1
We've verified that this works up to 4, so assume that n > 4 and the inequality holds for all values up to (but not including) n. The induction goes like this: 
T(n) ≤ 2 * T(n/2) + C*n
     ≤ 2 * (C+1) * n * log(n/2) + C*n
     = 2 * (C+1) * n/2 * ( log(n) – 1 ) + C*n
     = (C+1) * n * log(n) – (C+1) * n + C*n
     = (C+1) * n * log(n) – n
     < (C+1) * n * log(n)
and the induction is proved.

Order classes

The functions which characterize algorithm timing tend to fall into a few common ones: 
O(1)
O(log n)
O(n)
O(n * log n)
O(n2)
O(n2 * log n)
O(bn)          (each b generates a separate order class)
These order classes are upwardly inclusive, i.e., if T(n) = O(log n), then of course, T(n) = O(n). We're usually interested in the "best fit" in the sense of finding the smallest order class to which T(n) belongs.

In order to characterize the "best fit" of an order class, we need two other notions:

Lower bound: Ω

We say: 
T(n) = Ω(f(n))   or   T(n) is in Ω(f(n))
if there are constants C and k, such that 
T(n) ≥ C * f(n),  for all n ≥ k

Exact bound: Θ

We say: 
T(n) = Θ(f(n))   or   T(n) is in Θ(f(n))
if T(n) = O(f(n)) and T(n) = Ω(f(n))

This means that there are constants C1, C2 and k, such that 
C1 * f(n)  ≤  T(n)  ≤  C2 * f(n),  for all n ≥ k

Order Summary

Officially there are three considerations. Unofficially, the big-O terminology dominates the discussion of algorithmic analysis. Authors typically use O even when they mean Θ. If the exact order class is not know it means a true mathematical understanding is lacking.

Other algorithmic notations

The former (little-o) is used mostly to characterize the behavior of a function so as to say that "we can ignore it" relative to something else. For example, if 
T(n) = 100 * n + 200 * n2 + n3
We can igore all but the highest power term. In doing so, we might say: 
100 * n + 200 * n2 = o(n3)
The latter (exact match) is actually quite important, but unfortunately not explicitly defined in the Weiss textbook although the author uses is it on a number of occasions. For example, on page 5, he expresses these well-known mathematical facts: 
N*(N+1)/2 ≈ ½ N2        ∑i=1…N 1/i ≈ ln(N)
Authors are particularly keen on knowing the actual constants relative to the number of operations performed. For example, we can say that for linear search, counting the number of comparisons: 
linear search average case for successful search (n) = (n+1)/2 ≈ ½ n

Establishing relations for "different" functions

Any two really "different" functions like n, n2, log(n), 2n are in different order classes. The easiest proof often uses L'Hôpital's rule from calculus. For example: 
limx → ∞ log2(x)/x 
= limx → ∞log2(e) * ln(x)/x 
= limx → ∞ log2(e) * ln′(x) / x′
= limx → ∞ log2(e) * 1/x / 1 
= 0
and so 
log(n) = o(n)

Integer exponentiation

We want to write an algorithm to compute xn for an integer n ≥ 0. The obvious linear-time algorithm involves repeated multiplication by x. The more subtle version uses the binary representation of the exponent. The basis of the algorithm is this: 
n = 2 * n/2, if n even
n = 2 * n/2 + 1, if n odd
Throughout this section, for convenience, we'll represent integer truncated division by simple division, i.e., 
n/2  is really  flr(n/2)
Using properties of exponents, we have: 
x0 =  1
x1 =  x
and then we can write either: 
  1. n even: xn = (x2)n/2
n odd:  xn = x * (x2)n/2

  2. n even: xn = (xn/2)2
n odd:  xn = x * (xn/2)2
Both the "a" equations the "b" equations can lead to algorithms. Here is the full code: 
public static double powA(double x, int n) {
  if (n == 0) 
    return 1;
  if (n == 1) 
    return x;
  if (n % 2 == 0) 
    return powA( x * x, n/2 );
  //else
    return x * powA( x * x, n/2 );
}

public static double powB(double x, int n) {
  if (n == 0) 
    return 1;
  if (n == 1) 
    return x;
  double val = powB(x, n/2);
  if (n % 2 == 0) 
    return val * val;
  //else
    return x * val * val;
}

public static void main(String[] args) throws Exception {
  double x = 2.0;
  int n = 10;
  
  System.out.println(
    "powA(" + x + "," + n + ") = " + powA(x,n) 
    + "\n" +
    "powB(" + x + "," + n + ") = " + powB(x,n)
  );
}
The proof of correctness is more-or-less obvious for the recursive functions powA and powB. If we count each multiplication as "1", then, for the worst-case time function T(n), we compute: In either case, we get 
T(0) = 0
T(1) = 0
T(n) = T(n/2) + 2,   n ≥ 2
It can be proved by induction that: 
T(n) = O( log(n) )
Note that we were careful not to write the powB function like this: 
if (n % 2 == 0) 
  return powB(x, n/2) * powB(x, n/2);
else
  return x * powB(x, n/2) * powB(x, n/2);
The reason is that it would make the recurrence relation this: 
T(n) = 2 * T(n) + 2
and the 2 * T(n) factor causes T(n) to enter a different order class. It can be proved that 
T(n) = O( n * log(n) )

Proof of the iterative algorithm

Proving the correctness of an iterative algorithm is technically harder than the correctness of a recursive algorithm, which is more-or-less a straight-foroward induction proof. Here is the code: 
public static double powC(double x, int n) {
  double val = 1;
  while(n != 0) {
    if (n % 2 == 1) val *= x;
    n = n/2;
    x = x*x;
  }
  return val;
}
In particular, an iterative algorithm uses variables which change state in order to control the iteration. A proof requires that you establish a loop invariant, which is a logical statement expressed using the program variables so that: Let's look at the powC algorithm with some annotations: 
b = x; p = n;
double val = 1;
while(n != 0) {
  if (n % 2 == 1) val *= x;
  n = n/2;
  x = x*x;
}
The variables b (base) and p (power) represent the initial values of n and x, respectively. We want to argue that after the loop terminates: 
val = bp
The additional annotated variables b (base) and p are needed to express the invariant because x and n change state. The invariant we want is this: 
val * xn = bp
Clearly it is true initially. Assume it is true up to a certain point and then consider the next iteration step. Let val′, n′, and x′ be the new values of val, n and x, respectively, then: 
x′ = x * x
n′ = n/2
val′ = val * x, if n odd
     = val,     if n even
We must show: 
val′ * (x′)n′ = val * xn
There are two cases: The loop terminates when n equals 0, and so we get: 
val * x0 = bp, i.e., val = bp

Euclid's algorithm for GCD

Like most interesting algorithms, Euclid's algorithm has been widely studied. 
public static int gcd(int m, int n) {
  System.out.println( "gcd(" + m + "," + n + ")" );
  if (m==0 || m == n) return n;

  // so, m > 0 and m < n
  
  return gcd(n % m, m);
}

public static void main(String[] args) {
  int m = Integer.parseInt( javax.swing.JOptionPane.showInputDialog("First") );
  int n = Integer.parseInt( javax.swing.JOptionPane.showInputDialog("Second") );
    
  if (m > n) { int tmp=m; m=n; n=tmp; }   // swap m & n if m > n
  
  System.out.println( gcd(m,n) );  // guaranteed that m <= n
}
In order to argue various points about the algorithm, we need to know how the integer division operators ( / and % ) are defined. Assuming 0 < m, 
n/m = q   and   n % m = r
where q and r satisfy: 
n = m * q + r   where  r < m

Correctness

To show that gcd(m,n) = gcd(r,m), we argue this:
Claim: any common divisor of m,n is a common divisor of r,m, and vice-versa
Suppose d is a common divisor of m,n, then 
m = d * x   and   n = d * y
and so, 
r  =  n – m * q  =  d * x – d * y * q  =  d * ( x – y * q )
showing that d must be a divisor of r; thus d is a divisor of r,m. The converse argument is similar.

Time analysis

Let
T(n) = worst-case number of divisions to compute gcd(m,n), assuming n is the larger of the pair
We need to know something about the parameter values in the steps in gcd. Use the definition of quotient (q) and remainder and remainder (r) above. We claim: 
r = n % m ≤ flr(n/2)
There are two cases:
  1. m ≤ flr(n/2): Because r < m, it follows that r < flr(n/2)
  2. m > flr(n/2): Then we reason as follows. Let 
    x = n – m
    Then 
    x <  n – flr(n/2)  ≤  flr(n/2) + 1
    and so, 
    x ≤ flr(n/2) < m
    Writing the equation: 
    n = m * 1 + x
    since x < m, x must be the division remainder, r (and the quotient is 1), Thus r ≤ flr(n/2)
Now consider two steps in the computation: 
gcd( m, n ) 
            = gcd( r, m )   where  r = n % m
            = gcd( r1,r )   where  r1 = m % r
So after two steps, n has been replaced by r which is less than flr(n/2). Thus we can derive the recurrence relation: 
T(0) = 0
T(n) ≤ 2 + T( flr(n/2) ), n > 0
We can prove by induction that: 
T(n) ≤ 2 * log n, n ≥ 2
So we can say that T(n) = O(log n).

Further analysis

It is noted in the textbook that the constants Cworst and Cavg are of interest:
worst case # divisions for gcd(m,n) ≈ Cworst * log2(n)
average # divisions for gcd(m,n) ≈ Cavg * log2(n)
It can be shown that the worst case for gcd(m,n) occurs for a consecutive pair of Fibonacci numbers. Given that and other known facts about Fibonacci numbers, it is relatively easy to compute: 
Cworst = 1 / log2φ ≅ 1.44
where φ=(1+√5)/2 ≅ 1.62 is the so-called golden mean. Vastly more difficult is the analysis of the average case. According to the textbook, this constant is 
Cavg = 12 * (ln 2)2/ π2 ≅ .584
One final observations is that to truly analyze GCD, you cannot really count 1 for a division. In fact, the number of operations in a division step is linear in the number of digits in the dividend, i.e., the cost of dividing into n actually O(log n).

Maximum Subsequence Sum

The maximum subsequence problem starts with an array of integers (including negative values). The goal is to find a subsequence in the array with the largest sum. Here is a linear time, i.e., O(n), solution. The runtime is obvious, but the proof that it works is quite difficult.

The version here is basically what appears in the textbook. Other variables have been added in order to actually determine the start and endpoints of a maximal subsequence. The "answer", rather than simply the subsequence sum, consists of three values. In order to capture and deliver this information to the user, we construct an Answer object designed precisely for this algorithm. 
static class Answer {
  public int fromInd;
  public int toInd;
  public int sum;

  public Answer(int fromInd, int toInd, int sum) {
    this.fromInd = fromInd; this.toInd = toInd; this.sum = sum;
  }
  
  @Override
  public String toString() {
    return "sum: " + sum + ", from: " + fromInd + " to: " + toInd;
  }
}

static Answer maxsubsum(int[] A) {
  int maxSum = 0;
  int thisSum = 0;
  int i = 0, toInd = 0, fromInd = 0;
  for (int j = 0; j < A.length; ++j) {
    thisSum += A[j];

    if (thisSum > maxSum) {
      toInd = j;
      fromInd = i;
      maxSum = thisSum;
    } 
    else if (thisSum < 0) {
      thisSum = 0;
      i = j+1;
      System.out.println("i change: " + i);
    } 
  }
  return new Answer(fromInd, toInd, maxSum);
}

public static void main(String[] args) {
  int[] A = { -1, 4, -3, -7, 5, -2, 1, 2, 6, -2 };
    
  System.out.println( java.util.Arrays.toString( A ) );
  System.out.println( maxsubsum(A) );
}

Proof of correctness.

Use this notation: 
sum(p,q) = A[p] + A[p+1] + … + A[q-1]  // not including index q
maxSeqSum(a,b) = max∀i,j:a≤i≤j≤bsum(i,j)
So, we want to prove is that, when the loop terminates, 
maxSum = maxSeqSum(0,n)
The loop invariant is the conjunction (i.e., the logical and) of these clauses: 
thisSum = sum(i,j)
∀ p = i…j, sum(i,p) ≥ 0
maxSeqSum(0,n) = max( maxSeqSum(0,i), maxSeqSum(i,n) )
maxSum = maxSeqSum(0,j)
With these variable initializations it is trivial to verify that the invariant is true. 
i = j = 0;
thisSum = 0;
maxSum = 0;
Taking the iterative step, use prime (′) to represent the values of variables for the next iteration. In particular, j′ = j+1. There are two cases to consider:
  1. sum(i, j′) ≥ 0 So the first 3 clauses of the invariant are satisfied. Regarding the last clauses, there are two subcases:
    1. thisSum′ > maxSum
    2. thisSum′ ≤ maxSum
    In either case, 
    maxSum′ = maxSeqSum(0,j)
  2. sum(i,j′) < 0 The new i′ makes the first two clauses true. The last clause is OK as well. The hard part is arguing that the third clause remains valid. We must argue that: 
    maxSeqSum(i,n) = max( maxSeqSum(i,j+1), maxSumSeq(j+1,n) )
    There are two key points to understand this idea:

© Robert M. Kline