Computational Cost

If an algorithm executes in O(f(n)) time, this means it takes at worst an amount of resources proportional to f(n), where n is the size of the problem you are solving. The two resources: memory and time. (unit is bit-seconds).

Search a list for an element. Check every element. If the list has n items, you do n checks. O(n) (linear-time) algorithm.

Compute x**n with a simple loop, like so

def simple_power(x, n):
    if n < 0:
        x, n = 1/x, -n
    out = 1
    for k in range(n):
        out *= x
    return out

This is O(n).

In the smallest factor function we created, the shotgun method is O(n).

Using the sqaure-root principle, we chopped this down to O(sqrt(n)).

Bubble sort Begin by walking through the elements and swapping them if they are out of order.

                       p
6,-3, 4, 9, 7, -3, 4, 2
-3, 6, 4, 9, 7, -3, 4, 2
-3, 4, 6, 9, 7, -3, 4, 2
-3, 4, 6, 7, -3, 9, 4, 2
-3, 4, 6, 7, -3, 4, 9, 2
-3, 4, 6, 7, -3, 4, 2, 9
                     p
-3, 4, 6, 7, -3, 4, 2, 9
-3, 4, 6, -3, 7, 4, 2, 9
-3, 4, 6, -3, 4, 7, 2, 9
-3, 4, 6, -3, 4, 2, 7, 9
                  p
-3, 4, -3, 6, 4, 2, 7, 9
-3, 4, -3, 4, 6, 2, 7, 9
-3, 4, -3, 4, 2, 6, 7, 9
               p

-3, 4, -3, 4, 2, 6, 7, 9
-3, -3, 4, 4, 2, 6, 7, 9
-3, -3, 4, 2, 4, 6, 7, 9
            p

-3, -3, 4, 2, 4, 6, 7, 9
-3, -3, 2, 4, 4, 6, 7, 9
         p
-3, -3, 2, 4, 4, 6, 7, 9
      p
-3, -3, 2, 4, 4, 6, 7, 9
  p


list of length n
n - 1
n - 2
n - 3
.
.
.


1

n*(n-1)/2  O(n^2)  "Quadratic sort"

check if items are in order; if so, stop
if not shufffle
Repeat.


Suppose you perform independent experiments each with
probability p of sucess. Mean time to first success:  1/p

Mean time for bozo is n!

Bozo take O(n!) on the average

Computing a GCD with Euclid's Algorithm

Shotgun Approach


Theorem  If b, q, a and r are integers and if
b = a*q + r, then gcd(a,b) = gcd(a,r).

Let's apply this.