CPSC 2120 - DAY 4
MAY 16, 2016

===============================================================================


ANALYSIS OF ALGORITHMS

The objective is to measure either time or space requirements of an algorithm.

We simply count opertaions or units of space

Measure execution time in terms of any of the following...

	1. arithmetic opertaions
	2. assignment statements.
	3. loop iterations
	4. comparisons
	5. procedure calls

Floating point multiplication/division very cpu intensive
Floating pointing addition or subtraction not as intensive
1/30 difference 


Measure the space requirements in terms of number of bytes required by the
larger runtime data structures of the program.


order 1 algorithm - finding the largest element in a sorted array w/ n elements
                  Order O(1)   AKA CONSTANT COMPLEXITY

order n algorithm - finding the largest element in an unsorted array w/ n 
elements  AKA LINEAR COMPLEXITY

order n^2 algorithm - finding largest element nxn array unsorted.

order n^3 algorithm - finding largest element in nxnxn array unsorted

O(1) < O(n) < O(n^2) < O(n^3)

Sorted array

0   | |
1   | |
.   | |
.   | |
n-1 |_|

If you tried to examine every single element in the array to find the largest
it would be order n, rather than an order 1.

Binary Search - Split the array in half, check to see if your number is +/-
move either up or down, continuing to split the array in half until you reach
the number that you are searching for (requires sorted array ascending/
descending)

***NEED TO MAKE EXACTLY THREE COMPARISONS IN ORDER TO DETERMINE WHETHER OR NOT
AN ELEMENT IS IN AN ARRAY***

n     | # comp
______|_______
1     | 1
3     | 2
7     | 3  <- 2^n-1
15    | 4
31    | 5
63    | 6
127   | 7
255   | 8
2^k-1 | k


^Binary Search

Order logn time, double size of array, increase size by only one
EXTREMELY efficient O(log n)

O(1) < O(log n)< O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

BEST <-------------------------------------------------------> WORST


O(1)          - Constant
O(log n)      - logarithmic
O(n)          - linear
O(nlogn)      - 
O(n^2)        - quadratic
O(n^3)        - cubic
O(2^n)        - Exponential