CSC300: Counting, Approximation, Time Complexity, and Big Oh

(Click here for one slide per page)

In two parts

We are all used to counting by adding one (arithmetic series):

0 1 2 3 4 5 6 7 ... N

You can also count by multiplying by two (geometric series):

1 2 4 8 16 32 64 128 ... N

There is correspondence between these two forms of counting, called exponentiation.

      2^0  =    1       2^10 = 1024   ~ thousand    (kilo/kibi)
      2^1  =    2       2^20 = 1024^2 ~ million     (mega/mebi)
      2^2  =    4       2^30 = 1024^3 ~ billion     (giga/bigi)
      2^3  =    8       2^40 = 1024^4 ~ trillion    (tera/tebi)
      2^4  =   16       2^50 = 1024^5 ~ quadrillion (peta/pebi)
      2^5  =   32       2^60 = 1024^6 ~ quintillion (exa/ exbi)
      2^6  =   64 
      2^7  =  128       
      2^8  =  256  
      2^9  =  512 
      2^10 = 1024 

We are all used to counting by adding one (arithmetic series):

0 1 2 3 4 5 6 7 ... N

You can also count by multiplying by two (geometric series):

1 2 4 8 16 32 64 128 ... N

There is an inverse operation, called logarithm. People often write lg for the base 2 logarithm.

     lg(1) =    0     lg(thousand)    ~ 10
     lg(2) =    1     lg(million)     ~ 20
     lg(4) =    2     lg(billion)     ~ 30
     lg(8) =    3     lg(trillion)    ~ 40
    lg(16) =    4     lg(quadrillion) ~ 50
    lg(32) =    5     lg(quintillion) ~ 60
    lg(64) =    6
   lg(128) =    7
   lg(256) =    8
   lg(512) =    9
  lg(1024) =   10

These are equivalent:

  N = 2^k
  lg(N) = k

Log and exponentiation are inverses:

  lg(2^k) = k
  2^lg(N) = N

Breaking up exponents and logs:

 
  2^(k+j) = 2^k * 2^j
  lg(N*M) = lg(N) + lg(M)

Since

  2^(k+j) = 2^k * 2^j

we have:

   2^32 = 2^2 * 2^30 ~  4 billion     (actually              4_294_967_296)  
   2^64 = 2^4 * 2^60 ~ 16 quintillion (actually 18_446_744_073_709_551_616)

Since

  lg(N*M) = lg(N) + lg(M)

we have:

  lg(4 billion)      ~ lg(4)  + lg(billion)     = 2 + 30
  lg(16 quintillion) ~ lg(16) + lg(quintillion) = 4 + 60

In general, logs can have any base. Generally, we write log_b, where b is the base.

  log_b(N) = log_a(N) / log_a(b)

For example, where lg(n) = log_2(n):

  log_1024(N) = lg(N) / 10     --- since lg(1024) = 10

Another example, where log(n) = log_10(n):

  log(N) ~ lg(N) / 3           --- since lg(10) = 3.32192809489

This video might be helpful to some:

Here's a relaxing intro to logarithms you might like:

Often details are not important

We write f(n) ~ g(n) if f and g are more or less the same

• See Section 1.4 of Algorithms for a formal definition
• Roughly, they fit the same curve

We say f(n) is O(g(n)) if f(n) ~ a * g(n), for some constant a

• Called order of growth
• Called time complexity
• Called Big Oh

Image from 8 time complexities that every programmer should know by Adrian Mejia

Revised: 2008/03/17 13:01