complexity.ps

Data Structure Ebook

1 0 bop 262 307 a Fn(5)66 b(Complexit)n(y)262 398 y Fm(W)m(e)17
b(ha)o(v)o(e)h(already)g(used)h(the)f Fl(O)g Fm(notation)f(to)h(denote)
h(the)f(general)h(b)q(eha)o(viour)e(of)h(an)262 448 y(algorithm)11
b(as)j(a)g(function)f(of)h(the)g(problem)f(size.)19 b(W)m(e)14
b(ha)o(v)o(e)g(said)g(that)g(an)f(algorithm)f(is)262
498 y Fl(O)p Fm(\(log)6 b Fk(n)p Fm(\))15 b(if)f(its)h(running)f(time,)
g Fk(T)6 b Fm(\()p Fk(n)p Fm(\),)14 b(to)h(solv)o(e)g(a)f(problem)g(of)
g(size)i Fl(n)e Fm(is)h(prop)q(ortional)262 548 y(to)e(log)7
b Fk(n)p Fm(.)262 664 y Fj(5.1)55 b(The)19 b(O)f(notation)262
740 y Fm(F)m(ormally)l(,)10 b Fk(O)q Fm(\()p Fk(g)q Fm(\()p
Fk(n)p Fm(\)\))15 b(is)f(the)g Fi(set)g Fm(of)f(functions,)h
Fk(f)t Fm(,)g(suc)o(h)g(that)g(for)g(some)f Fk(c)e(>)h
Fm(0,)861 832 y Fk(f)t Fm(\()p Fk(n)p Fm(\))g Fk(<)g(cg)q
Fm(\()p Fk(n)p Fm(\))262 923 y(for)i(all)g(p)q(ositiv)o(e)h(in)o
(tegers,)h Fk(n)e(>)g(N)5 b Fm(,)15 b(ie)g(for)g(all)f(su\016cien)o
(tly)i(large)f Fk(N)5 b Fm(.)22 b(Another)16 b(w)o(a)o(y)e(of)262
973 y(writing)f(this)h(is:)866 1044 y(lim)852 1069 y
Fh(n)p Fg(!1)943 1016 y Fk(f)t Fm(\()p Fk(n)p Fm(\))p
943 1035 82 2 v 945 1073 a Fk(g)q Fm(\()p Fk(n)p Fm(\))1042
1044 y Ff(\024)e Fk(c)262 1143 y Fm(Informally)l(,)d(w)o(e)k(sa)o(y)f
(the)h Fk(O)q Fm(\()p Fk(g)q Fm(\))g(is)f(the)i(set)f(of)f(all)f
(functions)h(whic)o(h)h(gro)o(w)f Fi(no)i(faster)e Fm(than)262
1193 y Fk(g)q Fm(.)18 b(The)c(function)g Fk(g)h Fm(is)f(an)f
Fi(upp)n(er)i(b)n(ound)g Fm(to)f(functions)g(in)f Fk(O)q
Fm(\()p Fk(g)q Fm(\).)262 1243 y(W)m(e)g(are)i(in)o(terested)h(in)e
(the)g(set)h(of)f(functions)g(de\014ned)h(b)o(y)f(the)h
Fk(O)g Fm(notation)e(b)q(ecause)j(w)o(e)262 1293 y(w)o(an)o(t)h(to)i
(argue)f(ab)q(out)g(the)h(relativ)o(e)f(merits)g(of)g(algorithms)e(-)i
(indep)q(enden)o(t)h(of)f(their)262 1343 y(implem)o(en)o(tations.)g
(That)c(is,)g(w)o(e)h(are)g(not)g(concerned)h(with)e(the)i(language)d
(or)i(mac)o(hine)262 1392 y(used;)e(w)o(e)g(w)o(an)o(t)f(a)h(means)f
(of)g(comparing)f(algorithms)f(whic)o(h)j(is)g(relev)n(an)o(t)g(to)f
Fi(any)i Fm(imple-)262 1442 y(men)o(tation.)262 1492
y(W)m(e)f(can)h(de\014ne)h(t)o(w)o(o)e(other)i(functions:)j(\012\()p
Fk(g)q Fm(\))c(and)g(\002\()p Fk(g)q Fm(\))h(.)262 1542
y(\012\()p Fk(g)q Fm(\))g(the)h(set)g(of)f(functions)g
Fk(f)t Fm(\()p Fk(n)p Fm(\))h(for)f(whic)o(h)g Fk(f)t
Fm(\()p Fk(n)p Fm(\))g Ff(\025)f Fk(cg)q Fm(\()p Fk(n)p
Fm(\))i(for)e(all)g(p)q(ositiv)o(e)h(in)o(tegers,)262
1592 y Fk(n)c(>)h(N)5 b Fm(,)13 b(and)799 1691 y(\002\()p
Fk(g)q Fm(\))f(=)g(\012\()p Fk(g)q Fm(\))e Ff(\\)f Fk(O)q
Fm(\()p Fk(g)q Fm(\))262 1782 y(W)m(e)k(can)h(deriv)o(e:)897
1874 y Fk(f)i Ff(2)11 b Fm(\002\()p Fk(g)q Fm(\))262
1965 y(if)866 2070 y(lim)852 2095 y Fh(n)p Fg(!1)943
2042 y Fk(f)t Fm(\()p Fk(n)p Fm(\))p 943 2060 V 945 2098
a Fk(g)q Fm(\()p Fk(n)p Fm(\))1042 2070 y(=)h Fk(c)262
2186 y Fm(Th)o(us,)k(\012\()p Fk(g)q Fm(\))h(is)g(a)f(lo)o(w)o(er)g(b)q
(ound)g(-)g(functions)h(in)f(\012\()p Fk(g)q Fm(\))h(gro)o(w)f
Fi(faster)f Fm(than)i Fk(g)h Fm(and)e(\002\()p Fk(g)q
Fm(\))262 2235 y(are)g(functions)h(that)g(gro)o(w)f Fi(at)h(the)h(same)
f(r)n(ate)f Fm(as)h Fk(g)q Fm(.)26 b(In)17 b(these)h(last)e(t)o(w)o(o)g
(statemen)o(ts)h(-)262 2285 y(as)e(in)f(most)g(of)g(the)i(discussion)f
(on)g(complexit)o(y)e(theory)i(-)g("within)f(a)g(constan)o(t)i(factor")
262 2335 y(is)c(understo)q(o)q(d.)19 b(Di\013eren)o(t)13
b(languages,)f(compilers,)g(mac)o(hines,)f(op)q(erating)i(systems,)g
(etc)262 2385 y(will)c(pro)q(duce)j(di\013eren)o(t)f(constan)o(t)g
(factors:)17 b(it)10 b(is)h(the)g(general)g(b)q(eha)o(viour)g(of)f(the)
h(running)262 2435 y(time)h(as)i Fk(n)g Fm(increases)h(to)f(v)o(ery)g
(large)g(v)n(alues)f(that)h(w)o(e're)h(concerned)h(with.)967
2574 y(1)p eop
%%Page: 2 2
2 1 bop 262 307 a Fj(5.2)55 b(Prop)r(erties)17 b(of)i(the)f(O)h
(notation)262 384 y Fm(The)14 b(follo)o(wing)d(general)j(prop)q(erties)
i(of)d Fl(O)h Fm(notation)f(expressions)i(ma)o(y)d(b)q(e)i(deriv)o(ed:)
312 455 y(1.)20 b(Constan)o(t)14 b(factors)h(ma)o(y)c(b)q(e)k(ignored:)
365 519 y(F)m(or)f(all)e Fk(k)h(>)f Fm(0,)h Fl(kf)g Fm(is)h
Fl(O)p Fm(\()p Fk(f)t Fm(\).)365 582 y Fi(e.g.)h Fk(an)491
567 y Fe(2)523 582 y Fm(and)f Fk(bn)647 567 y Fe(2)679
582 y Fm(are)g(b)q(oth)g Fl(O)p Fm(\()p Fk(n)923 567
y Fe(2)942 582 y Fm(\).)312 660 y(2.)20 b(Higher)14 b(p)q(o)o(w)o(ers)h
(of)e Fl(n)h Fm(gro)o(w)f(faster)h(than)g(lo)o(w)o(er)g(p)q(o)o(w)o
(ers:)365 723 y Fk(n)390 708 y Fh(r)422 723 y Fm(is)g
Fl(O)p Fm(\()p Fk(n)541 708 y Fh(s)559 723 y Fm(\))g(if)f(0)e
Ff(\024)h Fk(r)g Ff(\024)g Fk(s)p Fm(.)312 800 y(3.)20
b(The)13 b(gro)o(wth)e(rate)i(of)e(a)g(sum)g(of)g(terms)h(is)g(the)g
(gro)o(wth)g(rate)g(of)f(its)h(fastest)h(gro)o(wing)365
850 y(term:)365 914 y(If)h Fl(f)f Fm(is)h Fl(O)p Fm(\()p
Fk(g)q Fm(\),)g(then)g Fl(f)i(+)g(g)e Fm(is)f Fl(O)p
Fm(\()p Fk(g)q Fm(\).)365 977 y Fi(e.g.)i Fk(an)491 962
y Fe(3)519 977 y Fm(+)9 b Fk(bn)603 962 y Fe(2)635 977
y Fm(is)14 b Fl(O)p Fm(\()p Fk(n)754 962 y Fe(3)772 977
y Fm(\).)312 1054 y(4.)20 b(The)13 b(gro)o(wth)g(rate)g(of)f(a)g(p)q
(olynomial)e(is)i(giv)o(en)g(b)o(y)h(the)g(gro)o(wth)g(rate)g(of)f(its)
h(leading)365 1104 y(term)h(\()p Fi(cf.)g Fm(\(2\),)g(\(3\)\):)365
1168 y(If)g Fl(f)f Fm(is)h(a)g(p)q(olynomial)c(of)j(degree)j
Fl(d)p Fm(,)c(then)j Fl(f)e Fm(is)h Fl(O)p Fm(\()p Fk(n)1196
1153 y Fh(d)1215 1168 y Fm(\).)312 1245 y(5.)20 b(If)d
Fl(f)f Fm(gro)o(ws)h(faster)g(than)g Fl(g)p Fm(,)g(whic)o(h)f(gro)o(ws)
h(faster)g(than)g Fl(h)p Fm(,)g(then)g Fl(f)f Fm(gro)o(ws)h(faster)365
1295 y(than)d Fl(h)p Fm(.)312 1372 y(6.)20 b(The)d(pro)q(duct)f(of)f
(upp)q(er)i(b)q(ounds)g(of)e(functions)h(giv)o(es)f(an)h(upp)q(er)h(b)q
(ound)f(for)f(the)365 1422 y(pro)q(duct)g(of)e(the)i(functions:)365
1485 y(If)f Fl(f)f Fm(is)h Fl(O)p Fm(\()p Fk(g)q Fm(\))g(and)g
Fl(h)f Fm(is)h Fl(O)p Fm(\()p Fk(r)q Fm(\),)f(then)i
Fk(f)t(h)g Fm(is)e Fl(O)p Fm(\()p Fk(g)q(r)q Fm(\))365
1549 y Fi(e.g.)i Fm(if)e Fl(f)g Fm(is)h Fl(O)p Fm(\()p
Fk(n)629 1534 y Fe(2)648 1549 y Fm(\))g(and)f Fl(g)h
Fm(is)g Fl(O)p Fm(\(log)6 b Fk(n)p Fm(\),)14 b(then)g
Fl(fg)g Fm(is)f Fl(O)p Fm(\()p Fk(n)1282 1534 y Fe(2)1308
1549 y Fm(log)6 b Fk(n)p Fm(\).)312 1626 y(7.)20 b(Exp)q(onen)o(tial)14
b(functions)g(gro)o(w)f(faster)i(than)e(p)q(o)o(w)o(ers:)365
1690 y Fk(n)390 1675 y Fh(k)424 1690 y Fm(is)h Fl(O)p
Fm(\()p Fk(b)536 1675 y Fh(n)559 1690 y Fm(\),)f(for)h(all)e
Fk(b)g(>)f Fm(1)p Fk(;)c(k)12 b Ff(\025)g Fm(0,)365 1753
y Fi(e.g.)j Fk(n)469 1738 y Fe(4)501 1753 y Fm(is)f Fl(O)p
Fm(\(2)616 1738 y Fh(n)638 1753 y Fm(\))g(and)g Fk(n)774
1738 y Fe(4)806 1753 y Fm(is)g Fl(O)p Fm(\()p Fk(exp)p
Fm(\()p Fk(n)p Fm(\)\).)312 1830 y(8.)20 b(Logarithms)12
b(gro)o(w)i(more)f(slo)o(wly)f(than)i(p)q(o)o(w)o(ers:)365
1894 y(log)419 1904 y Fh(b)443 1894 y Fk(n)f Fm(is)h
Fl(O)p Fm(\()p Fk(n)600 1879 y Fh(k)620 1894 y Fm(\))g(for)g(all)f
Fk(b)e(>)h Fm(1)p Fk(;)7 b(k)k(>)h Fm(0)365 1957 y Fi(e.g.)j
Fm(log)497 1968 y Fe(2)523 1957 y Fk(n)f Fm(is)f Fl(O)p
Fm(\()p Fk(n)680 1942 y Fe(0)p Fh(:)p Fe(5)725 1957 y
Fm(\).)312 2035 y(9.)20 b(All)13 b(logarithms)f(gro)o(w)h(at)h(the)h
(same)e(rate:)365 2098 y(log)419 2108 y Fh(b)443 2098
y Fk(n)g Fm(is)h(\002\(log)625 2108 y Fh(d)651 2098 y
Fk(n)p Fm(\))g(for)g(all)e Fk(b;)7 b(d)k(>)h Fm(1.)291
2175 y(10.)20 b(The)15 b(sum)d(of)i(the)g(\014rst)h Fl(n)e
Fk(r)803 2160 y Fh(th)851 2175 y Fm(p)q(o)o(w)o(ers)i(gro)o(ws)e(as)h
(the)h(\()p Fk(r)10 b Fm(+)g(1\))1352 2160 y Fh(th)1399
2175 y Fm(p)q(o)o(w)o(er:)903 2247 y Fh(n)884 2260 y
Fd(X)883 2349 y Fh(k)q Fe(=1)951 2299 y Fk(k)974 2282
y Fh(r)992 2299 y Fk(is)p Fm(\002\()p Fk(n)1098 2282
y Fh(r)q Fe([phone] y Fm(\))760 2435 y Fi(e.g.)839
2404 y Fd(P)883 2414 y Fh(n)883 2447 y(k)q Fe(=1)952
2435 y Fk(i)i Fm(=)1027 2415 y Fe(\()p Fh(n)p Fe(+1\))p
Fh(n)p 1027 2425 110 2 v 1073 2449 a Fe(2)1141 2435 y
Fk(is)p Fm(\002\()p Fk(n)1247 2420 y Fe(2)1266 2435 y
Fm(\)\))967 2574 y(2)p eop
%%Page: 3 3
3 2 bop 262 307 a Fj(5.3)55 b(P)n(olynomial)17 b(and)i(In)n(tractable)f
(Algorithms)262 384 y Fl(5.3.1)47 b(P)o(olynomial)13
b(time)h(complexit)o(y)262 460 y Fm(An)e(algorithm)e(is)i(said)g(to)g
(ha)o(v)o(e)h Fi(p)n(olynomial)g(time)g(c)n(omplexity)g(i\013)f
Fm(it)g(is)h Fl(O)p Fm(\()p Fk(n)1494 445 y Fh(d)1513
460 y Fm(\))f(for)g(some)262 510 y(in)o(teger)i Fl(d)p
Fm(.)262 618 y Fl(5.3.2)47 b(In)o(tractable)14 b(Algorithms)262
695 y Fm(A)g(problem)g(is)g(said)h(to)g(b)q(e)g Fi(intr)n(actable)f
Fm(if)g(no)h(algorithm)d(with)i(p)q(olynomial)e(time)h(com-)262
745 y(plexit)o(y)g(is)g(kno)o(wn)h(for)f(it.)18 b(W)m(e)c(will)e
(brie\015y)i(examine)f(some)g(in)o(tractable)h(problems)e(in)i(a)262
794 y(later)f(section.)967 2574 y(3)p eop
%%Page: 4 4
4 3 bop 262 307 a Fj(5.4)55 b(Analysing)19 b(an)g(algorithm)262
384 y Fl(5.4.1)47 b(Simple)14 b(Statemen)o(t)f(Sequence)262
460 y Fm(First)j(note)g(that)g(a)f(sequence)j(of)e(statemen)o(ts)g
(whic)o(h)f(is)h(executed)i(once)e(only)g(is)f Fl(O)p
Fm(\(1\).)262 510 y(It)k(do)q(esn't)h(matter)e(ho)o(w)h(man)o(y)f
(statemen)o(ts)h(are)h(in)f(the)h(sequence)h(-)e(only)g(that)g(the)262
560 y(n)o(um)o(b)q(er)12 b(of)g(statemen)o(ts)h(\(or)g(the)h(time)d
(that)i(they)h(tak)o(e)e(to)h(execute\))i(is)e(constan)o(t)g(for)g(all)
262 610 y(problems.)262 716 y Fl(5.4.2)47 b(Simple)14
b(Lo)q(ops)262 792 y Fm(If)f(a)h(problem)e(of)h(size)i
Fl(n)e Fm(can)i(b)q(e)f(solv)o(ed)g(with)f(a)h(simple)e(lo)q(op:)283
881 y Fc(for\(i=0;i<n;i++\))345 931 y Ff(f)h Fm(s;)h
Ff(g)262 1031 y Fm(where)h(s)g(is)g(an)f Fl(O)p Fm(\(1\))h(sequence)i
(of)d(statemen)o(ts,)h(then)g(the)g(time)f(complexit)o(y)f(is)h
Fl(nO)p Fm(\(1\))262 1081 y(or)f Fl(O)p Fm(\()p Fk(n)p
Fm(\).)262 1131 y(If)g(w)o(e)h(ha)o(v)o(e)g(t)o(w)o(o)f(nested)j(lo)q
(ops:)283 1178 y Fc(for\(j=0;j<n;j++\))345 1228 y Fm
(for\(i=0;i<n;i++\))428 1277 y Ff(f)d Fm(s;)h Ff(g)262
1377 y Fm(then)f(w)o(e)g(ha)o(v)o(e)g Fl(n)f Fm(rep)q(etitions)h(of)g
(an)f Fl(O)p Fm(\()p Fk(n)p Fm(\))h(sequence,)i(giving)c(a)h(complexit)
o(y)f(of:)17 b Fl(nO)p Fm(\()p Fk(n)p Fm(\))262 1427
y(or)c Fl(O)p Fm(\()p Fk(n)389 1412 y Fe(2)408 1427 y
Fm(\).)262 1477 y(Where)j(the)g(index)g('jumps')d(b)o(y)j(an)f
(increasing)h(amoun)o(t)d(in)j(eac)o(h)g(iteration,)f(w)o(e)h(migh)o(t)
262 1527 y(ha)o(v)o(e)d(a)h(lo)q(op)f(lik)o(e:)283 1574
y Fc(h)22 b(=)f(1;)262 1624 y Fm(while\()13 b(h)h Ff(\024)g
Fm(n)g(\))345 1674 y Ff(f)f Fm(s;)345 1723 y(h)g(=)i(2*h;)e
Ff(g)262 1771 y Fm(in)20 b(whic)o(h)g Fc(h)h Fm(tak)o(es)g(v)n(alues)g
(1,)g(2,)h(4,)g(...)38 b(un)o(til)19 b(it)i(exceeds)i
Fl(n)p Fm(.)38 b(This)21 b(sequence)h(has)262 1821 y(1)8
b(+)i Ff(b)p Fm(log)405 1831 y Fe(2)431 1821 y Fk(n)p
Ff(c)k Fm(v)n(alues,)f(so)h(the)g(complexit)o(y)e(is)i
Fl(O)p Fm(\(log)1104 1831 y Fe(2)1129 1821 y Fk(n)p Fm(\).)262
1871 y(If)f(the)i(inner)f(lo)q(op)f(dep)q(ends)i(on)f(an)g(outer)g(lo)q
(op)f(index:)262 1945 y Fc(for\(j=0;j<n;j++)o(\))349
1995 y(for\(i=0;i<j;i++\))436 2044 y({)21 b(s;)h(})262
2118 y Fm(The)14 b(inner)g(lo)q(op)f Fc(for\(i=0;)20
b(..)62 b Fm(gets)14 b(executed)i Fl(i)d Fm(times,)g(so)h(the)g(total)f
(is:)839 2177 y Fh(n)819 2190 y Fd(X)841 2277 y Fe(1)886
2229 y Fk(i)f Fm(=)961 2201 y Fk(n)p Fm(\()p Fk(n)d Fm(+)h(1\)\))p
961 2219 170 2 v 1035 2257 a(2)262 2350 y(and)17 b(the)i(complexit)o(y)
d(is)i Fl(O)p Fm(\()p Fk(n)760 2334 y Fe(2)779 2350 y
Fm(\).)30 b(W)m(e)18 b(see)h(that)f(this)h(is)e(the)i(same)e(as)h(the)h
(result)g(for)262 2399 y(t)o(w)o(o)c(nested)i(lo)q(ops)e(ab)q(o)o(v)o
(e,)h(so)f(the)i(v)n(ariable)d(n)o(um)o(b)q(er)h(of)g(iterations)h(of)f
(the)h(inner)g(lo)q(op)262 2449 y(do)q(esn't)e(a\013ect)h(the)f(`big)f
(picture'.)967 2574 y(4)p eop
%%Page: 5 5
5 4 bop 262 307 a Fm(Ho)o(w)o(ev)o(er,)12 b(if)g(the)i(n)o(um)o(b)q(er)
e(of)g(iterations)h(of)f(one)h(of)f(the)h(lo)q(ops)g(decreases)i(b)o(y)
e(a)f(constan)o(t)262 357 y(factor)h(with)h(ev)o(ery)h(iteration:)262
440 y Fc(h)21 b(=)h(n;)262 490 y(for\(j=0;j<h;j++)o(\))349
540 y({)349 589 y(for\(i=0;i<n;i++\))436 639 y({)f(s;)h(})349
689 y(h)f(=)h(h/2;)349 739 y(})262 822 y Fm(Then:)c(There)d(are)g(log)
629 832 y Fe(2)655 822 y Fk(n)f Fm(iterations)g(of)f(the)i(outer)f(lo)q
(op)f(and)h(the)h(inner)f(lo)q(op)f(is)h Fl(O)p Fm(\()p
Fk(n)p Fm(\),)262 872 y(so)j(the)i(o)o(v)o(erall)d(complexit)o(y)g(is)h
Fl(O)p Fm(\()p Fk(n)7 b Fm(log)g Fk(n)p Fm(\).)29 b(This)18
b(is)f(substan)o(tially)g(b)q(etter)i(than)f(the)262
922 y(previous)12 b(case)h(in)f(whic)o(h)g(the)h(n)o(um)o(b)q(er)e(of)h
(iterations)g(of)g(one)g(of)g(the)h(lo)q(ops)e(decreased)k(b)o(y)262
971 y(a)e(constan)o(t)i(for)e(eac)o(h)h(iteration!)272
1020 y Fb(c)262 1021 y Fa(\015)p Fb(John)f(Morris,)h(1996)967
2574 y Fm(5)p eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF