Performance Analysis

Document last modified:

Overview

Algorithms can be analyzed by performance several measures: run time and memory space being the most common.

Analyzing an Algorithm - means predicting the resources that the algorithm requires while working to solve its intended problem
number of instructions executed - Determine exactly how many instructions algorithm executes.
N - Size matters - takes into account the size of the problem the algorithm solves. Often the size of the problem is represented by the math variable N because the exact size is usually not known until run time.
f(N) - The result of the analysis is a mathematical function that is dependent on N. When f(N) is evaluated for a particular value (e.g., N = 1000), then the result is the number of instructions executed by the algorithm.
worst case analysis - When performing the analysis of an operation, there might be specific inputs that might make it execute very few instructions or many (e.g. sorting a sorted array might be relatively fast). An important analysis is then to determine which inputs make the algorithm perform the most possible instructions, i.e., make it perform at its worst with respect to time efficiency.
RAM model - random-access machine model
- instructions are executed one after another, (sequentially), with no concurrent operations
- contains instructions commonly found in real computers: arithmetic, data movement, and control
- each instruction takes a constant amount of time
- data types are integer and floating point
running time - the number of primitive instructions executed by an algorithm while it is working to solve an instance of a problem
input size - the size of the problem instance being solved by an algorithm; the running time is almost always stated as a dependence on the input size, e.g., a linear dependence.
worst-case running time
- the longest running time for any input of size N
- is an upper bound on the running time for any input
- provides a guarantee that the algorithm will never take any longer
rate of growth
- aka, order of growth
- a simplifying abstraction where we consider only the highest order term of the T(n) function that describes the an operation's running time
- we also ignore the highest order term's coefficient
- A computed run time of T(n) = 3n⁴+12n³-n²+1000 is said that T(n) = O(n⁴)
more efficient algorithm - we usually consider one algorithm to be more efficient than another if its worst case running time has a lower order growth (e.g. O(n) is more efficient that O(n⁴)).

Example - Constant Time Operation

The number of instructions executed by a constant time operation is not dependent on the size of the problem on which the operation is working.
Swap is an example of a constant time operation. O(1)

Swap (x, y)
-- alters x, y
-- post: x = old(y) and y = old(x)

Executions

1 temp ¬ x 1

2 x ¬ y 1

3 y ¬ temp 1

This operation correctly performs its function by executing exactly 3 statements, each constant time.
The size of the problem N would include the size of both integers that are being swapped.
The problem size of the Swap is for any N.
f(N) = 3 * N⁰ - since N raised to the power zero is 1, f(N) = 3
This is known as a constant function, where the slope is 0.
In Big-O notation, this operation is referred to as an O(1) operation or a constant time operation.

Example - Linear Time Operation

The number of instructions executed by a linear time operation is linearly dependent on the size of the problem on which the operation is working.
The Display operation for a Queue is an example of a linear time operation, O(n)

< "red" "C343" "Fall" >

Display (q)
-- preserves q
-- post: contents of q are displayed

          Executions

s1 i ¬ 1 1

s2 while i ≤ length[q] N+1

s3    x ¬ Dequeue (q) N

s4    print x N

s5    Enqueue (q, x) N

s6    i ¬ i + 1 N

The size of the problem N depends on the number of items in the queue.

N = length[q]

The first statement (s1) gets executed exactly 1 time no matter how many items are in the queue.

s1 contributes 1 * N⁰ instructions to the total.

Statement s2 gets executed N + 1 times.    Question: Why?

Statements s3, s4, s5, and s6, get executed N times

So these statements contribute 4 * N¹ instructions to the total

f(N) = (1 * N⁰) + (N¹ + 1) + (4 * N¹)
       = 5 * N¹ + 1 * N⁰=5 * N¹ + 1
=5N + 1

This is is a linear function where the slope is 5 and the y-intercept is 1.

In Big-O notation, this operation is referred to as an O(N) operation or a linear time operation.

5N + 1 is O(N)

Polynomial Time Operation

The number of instructions executed by a polynomial time operation is dependent on the size of the problem on which the operation is working.
The Insertion-Sort is an example of a polynomial time operation, O(n²)

The size of the problem N depends on the number of items in the array.

There are two loops, one nested within the other.

The best-case occurs when the array is sorted; the while is not iterated.

The worst-case occurs when the array is reverse sorted, O(n²)