CS 512 Test 3

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$1m4_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 Test 3 hdr(2, Test 3 - Asymptotic Analysis) hdr(3, CS 512, Algorithm Design)

Show the big-oh relation is transitive; that is, show if itl(f) = itl(O)(itl(g)) and itl(g) = itl(O)(itl(h)), then itl(f) = itl(O)(itl(h)). This question cannot be correctly answered with just a picture.
If itl(f) = itl(O)(itl(g)) then there exist constants itl(c1) > 0 and itl(N1) >= 0 such that
itl(f)(itl(n)) <= itl(c1)*itl(g)(itl(n))
for all itl(n) >= itl(N1). Similarly, if itl(g) = itl(O)(itl(h)) then there exist constants itl(c2) > 0 and itl(N2) >= 0 such that
itl(g)(itl(n)) <= itl(c2)*itl(h)(itl(n))
for all itl(n) >= itl(N2).
If itl(f)(itl(n)) <= itl(c1)*itl(g)(itl(n)) and itl(g)(itl(n)) <= itl(c2)*itl(h)(itl(n)) for the same value of itl(n), then itl(f)(itl(n)) <= itl(c1)*itl(c2)*itl(h)(itl(n)). The product itl(c1)*itl(c2) is greater than zero because each of itl(c1) and itl(c2) are. These facts lead to
itl(f)(itl(n)) <= itl(c3)*itl(h)(itl(n))
for the constant itl(c3) = itl(c1)*itl(c2) > 0 and all n >= itl(N3), where itl(N3) = max(itl(N1), itl(N2)). But this is just the definition of itl(f) = itl(O)(itl(h)).
The following argument is wrong; describe the error.
The function itl(f)(itl(n)) = itl(n) is Omega(itl(n)^2) because I can pick a constant itl(N) >= 0 such that for any itl(n) >= N, there exists a constant itl(c) > 0 such that itl(f)(itl(n)) >= itl(c)*itl(n)^2.
This question cannot be correctly answered with just a picture.
The error occurs in the choice of the constant itl(c): you must pick a single constant itl(c) that is valid for all values of itl(n) >= itl(N); you cannot pick and choose a value of itl(c) for each value of itl(n).
Derive an asymptotic estimate for the run-time of the following algorithm in terms of the size of the input array a:
```
i <- 0
do i < |a|/2
  j <- i + 1
  do j < |a| - 2
   if a[i] >= a[j]
     swap(a[i], a[j])
   or a[j] >= a[|a| - i - 1]
     swap(a[j], a[|a| - i - 1])
   fi
   j <- j + 1
  od
  i <- i + 1
od
```
Do not worry about what the algorithm does or whether or not it's correct; just derive an asymptotic estimate.
The first step is to assign asymptotic estimates to the simple statements, and to estimate the work done when evaluating the guards in the if and do statements:
```
Theta(1)
do i < |a|/2 Theta(1)
  Theta(1)
  do j < |a| - 2 Theta(1)
   if a[i] >= a[j] Theta(1)
     Theta(1)
   or a[j] >= a[|a| - i - 1] Theta(1)
     Theta(1)
   fi
   Theta(1)
  od
  Theta(1)
od
```
These estimates were produced under the assumption that it takes Theta(1) time to find the length of an array and to swap to variables.
The next step is to produce an estimate for the if statement. Each guard takes Theta(1) time to evaluate, as does the body of the associated branches; these two estimates combine to form a Theta(1) estimate for either branch, leading to a Theta(1) estimate for the whole if statement.
```
Theta(1)
do i < |a|/2 Theta(1)
  Theta(1)
  do j < |a| - 2 Theta(1)
   Theta(1)
   Theta(1)
  od
  Theta(1)
od
```
Simplify the loop-body estimate by adding adjacent Theta(1) estimates to get a Theta(1) estimate.
```
Theta(1)
do i < |a|/2 Theta(1)
  Theta(1)
  do j < |a| - 2 Theta(1)
   Theta(1)
  od
  Theta(1)
od
```
The inner-loop estimate needs a bound on the number of iterations, which means we need to bound the value of the expression |a| - 2. Ignoring the constant 2, the expression value can be bounded by Theta(itl(n)), where itl(n) = |a|. The loop-bound estimate and the loop-body estimate are multiplied together to form the estimate for the whole loop: Theta(itl(n))Theta(1) = Theta(itl(n)).
```
Theta(1)
do i < |a|/2 Theta(1)
  Theta(1)
  Theta(itl(n))
  Theta(1)
od
```
Simplify the outer-loop body by adding adjacent estimates.
```
Theta(1)
do i < |a|/2 Theta(1)
  Theta(itl(n))
od
```
The number of outer-loop iterations can also be bound by Theta(itl(n)), producing a Theta(itl(n))Theta(itl(n)) = Theta(itl(n)^2) estimate for the loop.
```
Theta(1)
Theta(itl(n)^2)
```
Simplify by combining adjacent estimates.
```
Theta(itl(n)^2)
```
If itl(f) is Theta(itl(g)), is it always true that itl(g) is Theta(itl(f))? Explain your answer. This question cannot be correctly answered with just a picture.
If itl(f) is Theta(itl(g)), then itl(f) is itl(O)(itl(g)), which means that, for some positive constant itl(c),
itl(f)(itl(n)) <= itl(c)*itl(g)(itl(n))
for all itl(n) >= itl(N) > 0. Because itl(c) is a positive constant, I can divide through the previous equation by 1/itl(c) to get
itl(c)'*itl(f)(itl(n)) <= itl(g)(itl(n))
where itl(c)' = 1/itl(c), for all itl(n) >= itl(N), which means that itl(g) is Omega(itl(f)).
If itl(f) is Theta(itl(g)), then itl(f) is Omega(itl(g)). By an argument similar to the one in the previous paragraph, itl(g) is itl(O)(itl(f)).
Because itl(g) is itl(O)(itl(f)) and itl(g) is Omega(itl(f)), itl(g) is Theta(itl(f)).

This page last modified on 15 i2m(10) 1999. 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,

m4_translit($2, , ,) ) }