Example #1 (loop counting): -----------------------------------------

Suppose we have the snippet of code:

for (int i=1 ; i<=N ; i*=2)
  for (int j=0 ; j<N ; ++j)
     // 1 step of work here

Then, in order to find the big-O runtime of these
nested loops, we track the outer loop's index
and the amount of work done by the inner blocks
for each of those outer loops:

  OL index        IL work
     1               N
     2               N
     4               N
     8               N
    ...                 in general, work == N
    N/4              N
    N/2              N
     N               N

The runtime is the sum of the "IL work" column:

N + N + N + N + ... + N + N + N    (and there are logN terms)

This is logN times N, which is    O(NlogN)

+---------------------------+
+  Ex1 Answer:  O(NlogN)    
+---------------------------+





Example #2 (recurrence relation): -----------------------------------------

Suppose we have the recurrence relation:

T(0) = 0
T(N) = N + 2T(N/2)

In order to find the big-O runtime of the algorithm
represented by T(N), we "unwind":


T(N) 

==  N + 2T(N/2)

==  N + 2( N/2 + 2T(N/4) )

==  N + 2( N/2 + 2( N/4 + 2T(N/8) ) )

... expanding to the base case yields ...

==  N + 2( N/2 + 2( N/4 + 2( N/8 + ...

==  N +   N    +    N   +    N   + ...  (with logN terms)

== O(NlogN)

+---------------------------+
+  Ex2 Answer:  O(NlogN)    
+---------------------------+






Problem #1 (loop counting): -----------------------------------------------

We have this snippet of code:

for (int i=1 ; i<=N ; i *= 2)
  for (int j=0 ; j<i ; ++j)
    // constant time (1 step) of work here




+---------------------------+
+  Pr1 Answer:  O()    
+---------------------------+







Problem #2 (loop counting): -----------------------------------------------

We have this snippet of code:

for (int i=1 ; i<=N ; ++i)
  for (int j=1 ; j<i ; j *= 2)
    // constant time (1 step) of work here




+---------------------------+
+  Pr2 Answer:  O()    
+---------------------------+








Problem #3 (recurrence relation): -----------------------------------------

Stoogesort!

T(0) = 0      # no comparisons if the list is 0 elements long
T(1) = 0      # no comparisons if the list is 1 element long
T(N) = something




+---------------------------+
+  Pr3 Answer:  O()    
+---------------------------+







Problem #4 (recurrence relation): -----------------------------------------

Stoogesort!

T(0) = 0
T(N) = N + 4*T(N/2)




+---------------------------+
+  Pr4 Answer:  O()    
+---------------------------+