Algorithm Analysis

Running Time

The Runtime of an algorithem can be determin eather experimental or theoretical. When the theoretical way is used, we need to count the primitive operations (basic computations: evaluating an expression, assigning variable, indexing into an array, calling a method, return from a method).

Algorithm arrayMax(A, n)    # operations
  currentMax ← A[0]               2
  for i ← 1 to n − 1 do           2 + n
    if A[i] > currentMax then     2(n − 1)
      currentMax ← A[i]           2(n − 1)
  { increment counter i}          2(n − 1)
  return currentMax               1

                            Total 7n − 1

To estimate the run time: Algorithm arrayMax executes 7n − 1 primitive operations in the worst case. Define:

  • a = Time taken by the fastest primitive operation
  • b = Time taken by the slowest primitive operation
  • Let T(n) be worst-case time of arrayMax. Then a (7n − 1) ≤ T(n) ≤ b(7n − 1)

Big-O Notation

O(1): describes an algorithm that will always execute in the same time (or space)
O(N): describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.
O(N^2): represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N3), O(N4) etc.
O(2N): denotes an algorithm whose growth doubles with each additon to the input data set. The growth curve of an O(2N) function is exponential - starting off very shallow, then rising meteorically. An example of an O(2N) function is the recursive calculation of Fibonacci numbers.
O(log N): for example the binary search. he iterative halving of data sets described in the binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase.

ADTs

  • An abstract data type (ADT) is an abstraction of a data structure
  • An ADT specifies:
    • Data stored
    • Operations on the data
    • Error conditions associated with operations

Exceptions

  • Attempting the execution of an operation of ADT may sometimes cause an error condition, called an exception
  • Exceptions are said to be “thrown” by an operation that cannot be executed