The “Order” of Performance: (Big) O
Basic idea:
Ignore constant factor: computer and language implementation details affect that: go for fundamental rate of increase with problem size.
Consider fastest growing term: Eventually, for large problems, it will dominate.
Value: Compares fundamental performance difference of algorithms
Caveat: For smaller problems, big-O worse performer may actually do better

T(n) = O(f(n))
T(n) = time for algorithm on input size n
f(n) = a simpler function that grows at about the same rate

Example: T(n) = 3n2+5n-17 = O(n2)
f(n) has faster growing term
no extra leading constant in f(n)

T(n) = O(f(n)) Defined
(n0 and
(c such that

If n > n0 then c·f(n) = T(n)

Example: T(n) = 3n2+5n-17
Pick c = 4, say; need 4n02 > 3n02+5n0-17
n02 > 5n0-17, for which n0 = 5 will do.

Efficiency of Algorithms

Efficiency of Algorithms

Efficiency Example 1
int find (int x[], int val) {
for (int i = 0; i