CS 201 - 10/21/14
Run Time of Algorithms
Classifications of Run Time (based on N data points)
1 or Constant Time
log log N
log N
N
N log N
N * N (N^2)
N * N * N (N^3)
...
Exponential (2^N)
An algorithm is O( NlogN )
"order of" or "big-Oh of"
Code for Binary Search (assumes array is already sorted)
assume sorted integer array, arr, of N values
int low, high, mid;
int target;
low = 0;
high = N - 1;
mid = (low + high) / 2;
while ( ( low < high ) && (arr[mid] != target) )
{
if ( arr[mid] < target )
{
low = mid + 1;
}
if ( arr[mid] > target )
{
high = mid - 1;
}
mid = (low + high) / 2;
}
What is the Big-Oh run time of a push onto a stack?
O (1) or O (C)
What is the Big-Oh run time of an insert into
a linked-list in which values are stored in
increasing order?
O(N)
What is the Big-Oh run time of
Scalar Matrix Mulitplication?
O(rows*columns)
What is the Big-Oh run time of
Scalar Square-Matrix Mulitplication?
O( rows^2 )