m4_divert(2) m4_define(_commentnesting, 0) m4_define(_begincomment,m4_dnl m4_ifelse(_commentnesting, 0, )) m4_define(_warning,m4_dnl _begincomment()This document was created by gen-_name.html Do not edit this document, edit gen-_name.html._endcomment()) m4_define(_hdrs, ) m4_define(_anchor_no, 0) m4_define(_abs, m4_ifelse(m4_eval($1 < 0), 1, m4_eval(-($1)), $1)) m4_define(hdr, _warning() $2 _warning() m4_ifelse(m4_eval($1 >= 0), 1, m4_define(`_hdrs', _hdrs`'_anchor_no $1 m4_translit(`$2', `,', ) )) m4_define(_anchor_no, m4_eval(_anchor_no + 1)) ) m4_define(usetag, _warning()$2_warning()) m4_define(puttag, _warning()$2_warning()) m4_changecom() m4_define(sps, $1$2) m4_define(sbs, $1$2) m4_define(,_warning()$1_warning()) m4_define(,_warning()$1_warning()) m4_define(itl,_warning()$1_warning()) m4_define(bld,_warning()$1_warning()) m4_define(hrf,_warning()$2_warning()) m4_define(mailat,_warning()hrf(mailto:$1,$1)_warning()) m4_define(nwsgrp, hrf(news:$1, $1)) m4_define(bookref, $1, $2. $3: $4, $5.) m4_define(i2m,m4_ifelse( $1,01,January, $1,02,February, $1,03,March, $1,04,April, $1,05,May, $1,06,June, $1,07,July, $1,08,August, $1,09,September, $1,10,October, $1,11,November,December)) m4_dnl $Revision: 1.5 $, $Date: 1999/12/09 19:16:32 $ CS 512 Homework 3 hdr(2, Homework 3 - Asymptotic Analysis) hdr(3, CS 512, Algorithm Design)

  1. Fill in the table
    100itl(n)^2log itl(n)1.3^itl(n)sin itl(n)
    100itl(n)^2
    log itl(n)
    1.3^itl(n)
    sin itl(n)
    so that each of the squares contains an omicron, theta, or omega to indicate the asymptotic relation between the function labeling the row containing the square and the function labeling the column containing the square.

    For example, the second square (in left to right order) on the top row would contain an omicron if 100itl(n)^2 is O(log itl(n)), or it would contain a omega if 100itl(n)^2 is Omega(log itl(n)), or it would contain a theta if 100itl(n)^2 is Theta(log itl(n)).

    You should put the strongest asymptotic relation possible in the squares; for example, it would be wrong to conclude that itl(f)(itl(n)) is itl(O)(itl(g)(itl(n))) when itl(f)(itl(n)) is Theta(itl(g)(itl(n))). You only need to deal with the big asymptotic relations big omicron, big theta, and big omega; you may ignore the little asymptotic relations little omicron and little omega.

    We can start with the observation that, for itl(c) = 1 and itl(N) = 0, itl(f) <= itl(f)(itl(n)) for all itl(n) >= 0, and so itl(f) = itl(O)(itl(f)). Similarly, itl(f) >= itl(f)(itl(n)) for all itl(n), and itl(f) = Omega(itl(f)). Because itl(f) = itl(O)(itl(f)) and itl(f) = Omega(itl(f)), then itl(f) = Theta(itl(f)), and that takes care of the main diagonal:

    100itl(n)^2log itl(n)1.3^itl(n)sin itl(n)
    100itl(n)^2
    log itl(n)
    1.3^itl(n)
    sin itl(n)
    Next, note that -1 <= sin itl(n) <= 1 for all values of itl(n). itl(n)^2, log itl(n), and 1.3^itl(n) are all monotone increasing functions and all are greater than 1 for itl(n) > 10 (assuming the base of the log is 10), so each function is an upper bound for sin itl(n), and sin itl(n) is a lower bound for each function:
    100itl(n)^2log itl(n)1.3^itl(n)sin itl(n)
    100itl(n)^2
    log itl(n)
    1.3^itl(n)
    sin itl(n)
    Theorem 1 tells us directly that itl(n)^2 = itl(O)(1.3^itl(n)), or
    itl(n)^2 <= c1.3^itl(n)
    for some c > 0 and any n >= N. Multiplying through by 100 gives
    100itl(n)^2 <= c'1.3^itl(n)
    where c' = 100c, and so 100itl(n)^2 = itl(O)(1.3^itl(n))
    100itl(n)^2log itl(n)1.3^itl(n)sin itl(n)
    100itl(n)^2
    log itl(n)
    1.3^itl(n)
    sin itl(n)
    Finaly, knowing that log itl(n) = itl(O)(itl(n)) and using transitivity fills in the rest of the table:
    100itl(n)^2log itl(n)1.3^itl(n)sin itl(n)
    100itl(n)^2
    log itl(n)
    1.3^itl(n)
    sin itl(n)

  2. The book defines little omega and little omicron, but it doesn't define little theta. Why doesn't the book define little theta?

    Working with an analogy from the big-letter notation, we might say that itl(f) is theta(itl(g)) if itl(f) is itl(o)(itl(g)) and itl(f) is omega(itl(g)), which is equivalent to saying that itl(g) is itl(o)(itl(f)). However, from the definition of itl(o)(), if itl(f) is itl(o)(itl(g)), then itl(g) can never be itl(o)(itl(f)) because itl(g) grows strictly faster than itl(f) - otherwise the limit itl(f)/itl(g) would diverge - which means the limit itl(g)/itl(f) does diverge, and so itl(g) is not itl(o)(itl(f)).

    It is possible to define little theta, and the definition most commonly used is that itl(f) is theta(itl(g)) if, as n tends towards infinity, the ratio itl(f)/itl(g) tends toward one.

  3. A complete, itl(n)-level binary tree is a binary tree in which all interior nodes have two children and all leaf nodes are at level itl(n). An algorithm itl(A) traverses a complete, itl(n)-level binary tree, doing a unit of work at each node. Define a recurrence relation itl(T)(itl(n)) which describes the total amount of work done by itl(A) when traversing a complete, itl(n)-level binary tree. Solve your recurrence relation to get an equation describing the amount of work done by itl(A).

    We want to define itl(T)(itl(n)), the amount of work done by the algorithm when processing a complete binary tree having itl(n) levels. Using the recursive structure of trees, a complete binary tree having itl(n) levels consists of a root node with two subtrees, each of which is a complete binary tree having itl(n) - 1 levels.

    The amount of work done by the algorithm when processing an itl(n)-level complete binary tree of follows directly from the recursive structure of trees: it does one unit of work for the root node, plus the amount of work it expends on the left subtree, plus the amount of work it expends on the right subtree, or

    itl(T)(itl(n))= 1 + itl(T)(itl(n) - 1) + itl(T)(itl(n) - 1)
    = 1 + 2itl(T)(itl(n) - 1)

    To set the base of the recurrence, note that the algorithm expends 1 unit of work on the complete binary tree with 0 levels:

    itl(T)(0) = 1

    Probably the easiest way to solve the recurrence

    (1)itl(T)(itl(n)) = 1 + 2itl(T)(itl(n) - 1)
    is to unroll it a few times and then guess at a pattern. The value of itl(T)(itl(n) - 1) is
    itl(T)(itl(n) - 1) = 1 + 2itl(T)(itl(n) - 2)
    which, when substituted back into equation (1) gives
    (2)itl(T)(itl(n))= 1 + 2(1 + 2itl(T)(itl(n) - 2))
    = 1 + 2 + 4itl(T)(itl(n) - 2))
    A pattern seems to be emerging, but let's unroll it one more time just to be sure. itl(T)(itl(n) - 2) = 1 + 2itl(T)(itl(n) - 3), which, when substituted into equation (2), gives
    itl(T)(itl(n))= 1 + 2 + 4(1 + 2itl(T)(itl(n) - 3))
    = 1 + 2 + 4 + 8itl(T)(itl(n) - 3))
    At this point it seems safe to guess that
    (3)itl(T)(itl(n)) = sum(i = 0 to itl(n), 2^i)
    where sum() is an alternative representation of the usual sigma notation; that is,
    sum(i = 0 to itl(n), 2^i) = 2^0 + 2^1 + ... + 2^itl(n)

    But we're not done yet. It's one thing to guess that equation (3) is true, it's quite another thing to prove it's true. The easiest way to prove equation (3) is true is by induction. The base case for the induction follows from the base case for the recurrence and a few simple identities:

    itl(T)(0) = 1 = 2^0 = sum(i = 0 to 0, 2^i)

    Now for the inductive step. Assume for some itl(j) >= 0

    (4)itl(T)(itl(j)) = sum(i = 0 to itl(j), 2^i)
    The value of itl(T)(itl(j) + 1) is, by the definition of the recurrence
    (5)itl(T)(itl(j) + 1) = 1 + 2itl(T)(itl(j))
    Substituting equation (4) into equation (5) gives
    itl(T)(itl(j) + 1) = 1 + 2sum(i = 0 to itl(j), 2^i)
    Replacing sum() by its definition gives
    itl(T)(itl(j) + 1) = 1 + 2(2^0 + 2^1 + ... + 2^itl(j))
    Carrying through the multiplication gives
    itl(T)(itl(j) + 1) = 1 + 2^1 + 2^2 + ... + 2^(itl(j) + 1)
    Recognizing that 1 = 2^0, we can re-establish the sum() notation
    (6)itl(T)(itl(j) + 1) = sum(i = 0 to itl(j) + 1, 2^itl(i))
    and this is what we needed to prove.

    At the risk of putting too fine a point on it, there's one more step we can take. Equation (6) is not particularly convenient to use because computing the sum() function is rather involved (although not difficult). Is it possible to find a equivalent but simpler form for the right-hand side of equation (6)?

    Taking a tip from the approach we used to solve the recurrence, let's unroll the first few values of sum to see if there's a pattern

    sum(i = 0 to 0, 2^i)= 1= 1
    sum(i = 0 to 1, 2^i)= 1 + 2= 3
    sum(i = 0 to 2, 2^i)= 1 + 2 + 4= 7
    sum(i = 0 to 3, 2^i)= 1 + 2 + 4 + 8= 15
    sum(i = 0 to 4, 2^i)= 1 + 2 + 4 + 8 + 16= 31
    So it would seem that
    sum(i = 0 to itl(n), 2^i)= 2^(itl(n) + 1) - 1
    As always, however, a guess is not a proof, for which we'll turn once again to induction. The base case when itl(n) = 0 is easy:
    sum(i = 0 to 0, 2^itl(i)) = 1 = 2 - 1 = 2^1 - 1 = 2^(0 + 1) - 1
    For the inductive step assume the inductive hypothesis holds for some itl(j) >= 0 and consider the value of sum(i = 0 to j + 1, 2^itl(i)):
    sum(i = 0 to j + 1, 2^itl(i)) = sum(i = 0 to j, 2^itl(i)) + 2^(itl(j) + 1)
    from the definition of sum(). Substituting the inductive hypothesis, which is true for itl(j), gives
    sum(i = 0 to j + 1, 2^itl(i)) = 2^itl(j + 1) - 1 + 2^(itl(j) + 1)
    A little algebra gives
    sum(i = 0 to j + 1, 2^itl(i)) = 2(2^(itl(j) + 1)) - 1 = 2^(itl(j) + 2) - 1
    which is what we needed to prove.

    Finely we can conclude that

    itl(T)(itl(n)) = 2^(itl(n) + 1) - 1

  4. Analyze the function 
     sum_array(a)

  sum <- 0
  i <- 1
  do i <= |a|
    j <- a[i]
    do j > 0
      sum <- sum + 1
      j <- j - 1
    od
    i <- i + 1
  od

  return sum
    and derive an asymptotic expression of its run time on an input array of length itl(n).

    The first thing to do is replace the simple statements with their asymptotic approximations, and determine how much work a loop itself does on each iteration: 

    Theta(1)
Theta(1)
do i <= |a| Theta(1)
  Theta(1)
  do j > 0 Theta(1)
    Theta(1)
    Theta(1)
  od
  Theta(1)
od
Theta(1)
    This analysis assumes the array size operator |a| can be performed in constant time, which is usually - but not always - a safe assumption (for example, if a is an array of characters and you're using the C computational model, then the array size operator is strlen() and would take Theta(n) time to perform).

    Next use sequence combination to simplify things a bit, folding the work done by each loop on each iteration into the work done by the loop body: 

    Theta(1)
do i <= |a|
  Theta(1)
  do j > 0
    Theta(1)
  od
  Theta(1)
od
Theta(1)

    Now we have to bound the number of iterations done by each loop, starting with the inner-most loop. Bounding the inner loop requires putting a bound on the value of j, which is equivalent to putting a bound on the value of a[i].

    The problem statement doesn't say anything about the values contained in a, apart from the implicit assumption that they're some kind of numbers, so we have to appeal to our computational model for a bound. It seems reasonable to assume that there is a constant, maximum representable value larger than which a[i] cannot be, and therefore that the inner loop has a constant - and tight - bound on the number of iterations it could perform.

    There are a few interesting notes to point out before going on with the analysis. The first is that the tight Theta(1) bound on the number of iterations has a sizeable constant: for the usual 32-bit representation of integers, the constant is around 4 billion. This looks like a good place to use the Manber's suggested double-oh (or infinite) notation to indicate an upper bound with a possibly unacceptably large constant.

    Second, the assumption of a constant maximum representable value holds for many different computational models. Even a computational model that supports arbitrary precision big-nums - such as many Lisp systems and the Unix desk calculator dc - can only represent numbers that fit into the machine's storage, resulting in a ridiculously large - but still constant - upper bound. An assumption that holds under a wide variety of models is usually considered a good assumption, although it may also be considered bad if it leads to ridiculous but legitimate results.

    In any event, back to the analysis. Replacing the inner loop with its multiplicative asymptotic estimate gives 

    Theta(1)
do i <= |a|
  Theta(1)
  Theta(1)*Theta(1)
  Theta(1)
od
Theta(1)
    which simplifies to 
    Theta(1)
do i <= |a|
  Theta(1)
od
Theta(1)
    The outer loop is bounded by the size of the input array, that is, by n: 
    Theta(1)
Theta(n)*Theta(1)
Theta(1)
    Simplifying one more time gives a Theta(n) bound on execution time.

This page last modified on 18 i2m(01) 2000. m4_dnl $Revision: 1.2 $, $Date: 1999/03/12 17:36:48 $ m4_divert(1) m4_changequote({, }) {m4_define(tblfcntnts, _toc_tableit(}_hdrs{) _toc_down(_toc_ilevel, _toc_level) ) m4_define(_toc_tableit, m4_regexp($1, \([0-9]+\) \([0-9]+\) \([^ ]+\) \(.*\), m4_ifdef(_toc_level, , m4_define(_toc_level, m4_eval(\2 - 1)) m4_define(_toc_ilevel, _toc_level)) _toc_entry(\1, \2, \3) _toc_tableit(\4)) ) m4_define(_toc_down, m4_ifelse(m4_eval($1 < $2), 1, _toc_down($1, m4_eval($2 - 1))) ) m4_define(_toc_entry, m4_ifelse(m4_eval($2 > _toc_level),1,