Algorithm Analysis Introduction
An algorithm is a sequence of steps for performing a task in a finite amount of time.
The following properties of algorithms are in order of importance:
- Running Time (Time Complexity)
- Memory Usage (Space Complexity)
- Optimality of the output solution.
Experimental Analysis of Algorithms
This is the collection of empirical data at runtime.
The running time depends on the size and instance of the input and the algorithm used where:
- Size - The number of inputs in a list.
- Instance - The state of the inputs:
- Optimal and worst-case scenarios.
Drawbacks of Experimental Analysis
- Experiments are performed on a limited set of test inputs.
- Requires all tests to be performed using same hardware and software.
- Requires implementation and execution of algorithm.
Theoretical Analysis
Benefits over Experimental Analysis
- Can take all possible inputs into account.
- Can compare efficiency of many algorithms, independent of hardware/software environment.
- Involves studying high-level descriptions of algorithms:
- Pseudo-code
Language to Describe Algorithms
We use pseudo-code as a high-level description language for algorithms like so:
Minimum-Element(A)
/** Find the minimum of elements in the array A. **/
min ← A[1]
for j ← 2 to length[A]
do
/* Compare element A[j] to current min
and store it if it’s smaller. */
if A[j] < min
then min ← A[j]
return min
This course will not use a strict method for defining pseudo-code. It should however be clear as to not be misinterpreted.
Computational Model
This course will use a Random Access Machine (RAM) model that is comprised of the following components:
- CPU
- RAM
- A bank of memory cells, each of wuich can store a number, character, or address.
Primitive operations like:
- Single Addition
- Multiplication
- Comparison
take constant time to run.
This is not true in physical CPUs, it is just an assumption.
Measuring Running Time
To measure running time we count the primitive operations. We can do this using the previous example:
Minimum-Element(A)
min ← A[1] # O(1)
for j ← 2 to length[A] # O(n - 1)
do
# Compare element A[j] to current min
# and store it if it’s smaller.
if A[j] < min # O(n - 1)
then min ← A[j] # O(n - 1)
return min # O(n)
This sums to give:
\[3(n-1)+2\]Characterising Running Time
An algorithm may run faster on some inputs compared to others.
- Average-Case Complexity - Running time as an average taken over all inputs of the same size.
- Worst-Case Complexity - Running time as the maximum taken over all inputs of the same size.
Usually, we’re most interested in worst-case complexity.