Asymptotic notation

Growth Functions and Asymptotic Notation

1. Asymptotic Notation 1
GrowthofFunctionsand
AymptoticNotation
•Whenwestudyalgorithms,weareinterestedin
characterizing themaccording totheirefciency.
•Weareusuallyinterestingintheorder ofgrowth
oftherunningtimeofanalgorithm,notinthe
exact runningtime. Thisisalsoreferred toasthe
asymptoticrunningtime.
•Weneedtodevelop awaytotalkaboutrateof
growthoffunctionssothatwecancompare
algorithms.
•Asymptoticnotationgivesusamethodfor
classifyingfunctionsaccording totheirrateof
growth.

2. Asymptotic Notation 2
Big-ONotation
•DeΘnition:f(n) =O(g(n))iffthere aretwo
positiveconstantscandn0suchthat
|f(n)| ≤c|g(n)|foralln≥n0
•Iff(n)isnonnegative, wecansimplifythelast
conditionto
0≤f(n)≤cg(n)foralln≥n0
•Wesaythat“f(n)isbig-Oofg(n).”
•Asnincreases,f(n)growsnofaster thang(n).
Inotherwords,g(n)isanasymptoticupper
boundonf(n).
f(n) = O(g(n))
n0
cg(n)
f(n)

3. Asymptotic Notation 3
Example:n
2
+n=O(n
3
)
Proof:
•Here, wehavef(n) =n
2
+n,andg(n) =n
3
•Noticethatifn≥1,n≤n
3
isclear.
•Also,noticethatifn≥1,n
2
≤n
3
isclear.
•SideNote:Ingeneral, ifa≤b,thenn
a
≤n
b
whenevern≥1. Thisfactisusedofteninthese
typesofproofs.
•Therefore,
n
2
+n≤n
3
+n
3
= 2n
3
•Wehavejustshownthat
n
2
+n≤2n
3
foralln≥1
•Thus,wehaveshownthatn
2
+n=O(n
3
)
(bydeΘnitionofBig-O,withn0= 1,andc= 2.)

4. Asymptotic Notation 4
Big-Ωnotation
•DeΘnition:f(n) = Ω(g(n))ifftherearetwo
positiveconstantscandn0suchthat
|f(n)| ≥c|g(n)|foralln≥n0
•Iff(n)isnonnegative, wecansimplifythelast
conditionto
0≤cg(n)≤f(n)foralln≥n0
•Wesaythat“f(n)isomegaofg(n).”
•Asnincreases,f(n)growsnoslowerthang(n).
Inotherwords,g(n)isanasymptoticlowerbound
onf(n).
n0
cg(n)
f(n)
f(n) = O(g(n))

5. Asymptotic Notation 5
Example:n
3
+4n
2
=Ω(n
2
)
Proof:
•Here, wehavef(n) =n
3
+4n
2
,andg(n) =n
2
•Itisnottoohardtoseethatifn≥0,
n
3
≤n
3
+4n
2
•Wehavealready seenthatifn≥1,
n
2
≤n
3
•Thuswhenn≥1,
n
2
≤n
3
≤n
3
+4n
2
•Therefore,
1n
2
≤n
3
+4n
2
foralln≥1
•Thus,wehaveshownthatn
3
+4n
2
= Ω(n
2
)
(bydeΘnitionofBig-Ω,withn0= 1,andc= 1.)

6. Asymptotic Notation 6
Big-Θnotation
•DeΘnition:f(n) = Θ(g(n))iffthereare three
positiveconstantsc1,c2andn0suchthat
c1|g(n)| ≤ |f(n)| ≤c2|g(n)|foralln≥n0
•Iff(n)isnonnegative, wecansimplifythelast
conditionto
0≤c1g(n)≤f(n)≤c2g(n)foralln≥n0
•Wesaythat“f(n)isthetaofg(n).”
•Asnincreases,f(n)growsatthesamerateas
g(n). Inotherwords,g(n)isanasymptotically
tightboundonf(n).
c
2
g(n)
c
1
g(n)
f(n)
n
0

7. Asymptotic Notation 7
Example:n
2
+5n+7=Θ(n
2
)
Proof:
•Whenn≥1,
n
2
+5n+7≤n
2
+5n
2
+7n
2
≤13n
2
•Whenn≥0,
n
2
≤n
2
+5n+7
•Thus,whenn≥1
1n
2
≤n
2
+5n+7≤13n
2
Thus,wehaveshownthatn
2
+5n+7 = Θ(n
2
)
(bydeΘnitionofBig-Θ,withn0= 1,c1= 1,and
c2= 13.)

8. Asymptotic Notation 8
ArithmeticofBig-O,Ω,andΘnotations
•Transitivity:
–f(n)∈O(g(n))and
g(n)∈O(h(n))⇒f(n)∈O(h(n))
–f(n)∈Θ(g(n))and
g(n)∈Θ(h(n))⇒f(n)∈Θ(h(n))
–f(n)∈Ω(g(n))and
g(n)∈Ω(h(n))⇒f(n)∈Ω(h(n))
•Scaling: iff(n)∈O(g(n))thenforany
k >0,f(n)∈O(kg(n))
•Sums: iff1(n)∈O(g1(n))and
f2(n)∈O(g2(n))then
(f1+f2)(n)∈O(max(g1(n),g2(n)))

9. Asymptotic Notation 9
StrategiesforBig-O
•Sometimestheeasiestwaytoprove that
f(n) =O(g(n))istotakectobethesumofthe
positivecoefΘcients off(n).
•Wecanusuallyignorethenegative coefΘcients.
Why?
•Example:Toprove5n
2
+3n+20 =O(n
2
),we
pickc= 5+3+20 = 28. Thenifn≥n0= 1,
5n
2
+3n+20≤5n
2
+3n
2
+20n
2
= 28n
2
,
thus5n
2
+3n+20 =O(n
2
).
•Thisisnotalways soeasy. Howwouldyoushow
that(
√
2)
logn
+log
2
n+n
4
isO(2
n
)? Orthat
n
2
=O(n
2
−13n+23)? After wehave talked
abouttherelative ratesofgrowthofseveral
functions,thiswillbeeasier.
•Ingeneral, wesimply(or,insomecases, with
mucheffort)Θndvaluescandn0thatwork. This
getseasier withpractice.

10. Asymptotic Notation 10
StrategiesforΩandΘ
•Provingthataf(n) = Ω(g(n))oftenrequires
morethought.
–Quiteoften,wehave topickc <1.
–Agoodstrategyistopickavalueofcwhich
youthinkwillwork, anddetermine which
valueofn0isneeded.
–Beingabletodoalittlealgebra helps.
–Wecansometimessimplifybyignoringterms
of f ( n) withthepositivecoefΘcients.Why?
•Thefollowingtheoremshowsusthatproving
f(n) = Θ(g(n))isnothingnew:
– Theorem:f(n) = Θ(g(n))ifandonlyif
f(n) =O(g(n))andf(n) = Ω(g(n)).
–Thus,wejustapplytheprevioustwo
strategies.
•Wewillpresentafewmoreexamples usinga
several differentapproaches.

11. Asymptotic Notation 11
Showthat
1
2
n
2
+3n=Θ(n
2
)
Proof:
•Noticethatifn≥1,
1
2
n
2
+3n≤
1
2
n
2
+3n
2
=
7
2
n
2
•Thus,
1
2
n
2
+3n=O(n
2
)
•Also,whenn≥0,
1
2
n
2
≤
1
2
n
2
+3n
•So
1
2
n
2
+3n= Ω(n
2
)
•Since
1
2
n
2
+3n=O(n
2
)and
1
2
n
2
+3n= Ω(n
2
),
1
2
n
2
+3n= Θ(n
2
)

12. Asymptotic Notation 12
Showthat(nlogn−2n+13)=Ω(nlogn)
Proof:Weneedtoshowthatthereexistpositive
constantscandn0suchthat
0≤cnlogn≤nlogn−2n+13foralln≥n0.
Sincenlogn−2n≤nlogn−2n+13,
wewillinsteadshowthat
cnlogn≤nlogn−2n,
whichisequivalentto
c≤1−
2
logn
,whenn >1.
Ifn≥8,then2/(logn)≤2/3,andpickingc= 1/3
sufΘces. Thusifc= 1/3andn0= 8,thenforall
n≥n0,wehave
0≤cnlogn≤nlogn−2n≤nlogn−2n+13.
Thus(nlogn−2n+13) = Ω(nlogn).

13. Asymptotic Notation 13
Showthat
1
2
n
2
−3n=Θ(n
2
)
Proof:
•WeneedtoΘndpositiveconstantsc1,c2,andn0
suchthat
0≤c1n
2
≤
1
2
n
2
−3n≤c2n
2
foralln≥n0
•Dividingbyn
2
,weget
0≤c1≤
1
2
−
3
n
≤c2
•c1≤
1
2
−
3
n
holdsforn≥10andc1= 1/5
•
1
2
−
3
n
≤c2holdsforn≥10andc2= 1.
•Thus,ifc1= 1/5,c2= 1,andn0= 10,thenfor
alln≥n0,
0≤c1n
2
≤
1
2
n
2
−3n≤c2n
2
foralln≥n0.
Thuswehaveshownthat
1
2
n
2
−3n= Θ(n
2
).

14. Asymptotic Notation 14
AsymptoticBoundsandAlgorithms
•Inalloftheexamplessofar,wehaveassumedwe
knewtheexact runningtimeofthealgorithm.
•Ingeneral, itmaybevery difΘculttodetermine
theexact runningtime.
•Thus,wewilltrytodetermineaboundswithout
computingtheexact runningtime.
•Example:Whatisthecomplexityofthe
followingalgorithm?
for (i = 0; i < n; i ++)
for (j = 0; j < n; j ++)
a[i][j] = b[i][j] * x;
Answer:O(n
2
)
•Wewillseemoreexamples later.

15. Asymptotic Notation 15
SummaryoftheNotation
•f(n)∈O(g(n))⇒fg
•f(n)∈Ω(g(n))⇒fg
•f(n)∈Θ(g(n))⇒f≈g
•Itisimportanttoremember thataBig-Oboundis
onlyanupperbound. Soanalgorithmthatis
O(n
2
)mightnotever takethatmuchtime. Itmay
actuallyruninO(n)time.
•Conversely, anΩboundisonlyalowerbound. So
analgorithmthatisΩ(nlogn)mightactuallybe
Θ(2
n
).
•Unliketheotherbounds,aΘ-boundisprecise. So,
ifanalgorithmisΘ(n
2
),itrunsinquadratic time.

16. Asymptotic Notation 16
CommonRatesofGrowth
Inorder forustocomparetheefΘciency ofalgorithms,
weneedtoknowsomecommongrowthrates,andhow
theycompare tooneanother. Thisisthegoalofthe
nextseveral slides.
Letnbethesizeofinputtoanalgorithm,andksome
constant. Thefollowingare commonrates ofgrowth.
•Constant:Θ(k),forexampleΘ(1)
•Linear:Θ(n)
•Logarithmic:Θ(log
kn)
•nlogn:Θ(nlog
kn)
•Quadratic:Θ(n
2
)
•Polynomial:Θ(n
k
)
•Exponential:Θ(k
n
)
We'lltakeacloser lookateach oftheseclasses.

17. Asymptotic Notation 17
ClassiΘcationofalgorithms-Θ(1)
•Operations areperformedktimes,wherekis
someconstant,independent ofthesizeofthe
inputn.
•Thisisthebestonecanhopefor,andmostoften
unattainable.
•Examples:
int Fifth_Element(int A[],int n) {
return A[5];
}
int Partial_Sum(int A[],int n) {
int sum=0;
for(int i=0;i<42;i++)
sum=sum+A[i];
return sum;
}

18. Asymptotic Notation 18
ClassiΘcationofalgorithms-Θ(n)
•Runningtimeislinear
•Asnincreases, runtimeincreases inproportion
•Algorithmsthatattainthislookateachofthen
inputsatmostsomeconstantktimes.
•Examples:
void sum_first_n(int n) {
int i,sum=0;
for (i=1;i<=n;i++)
sum = sum + i;
}
void m_sum_first_n(int n) {
int i,k,sum=0;
for (i=1;i<=n;i++)
for (k=1;k<7;k++)
sum = sum + i;
}

19. Asymptotic Notation 19
ClassiΘcationofalgorithms-Θ(logn)
•Alogarithmicfunctionistheinverse ofan
exponential function,i.e.b
x
=nisequivalentto
x= log
bn)
•Always increases, butataslowerrateasn
increases. (Recall thatthederivativeoflognis
1
n
,
adecreasing function.)
•Typicallyfoundwhere thealgorithmcan
systematicallyignorefractions oftheinput.
•Examples:
int binarysearch(int a[], int n, int val)
{
int l=1, r=n, m;
while (r>=1) {
m = (l+r)/2;
if (a[m]==val) return m;
if (a[m]>val) r=m-1;
else l=m+1; }
return -1;
}

20. Asymptotic Notation 20
ClassiΘcationofalgorithms-Θ(nlogn)
•CombinationofO(n)andO(logn)
•Foundinalgorithmswhere theinputisrecursively
brokenupintoaconstantnumberofsubproblems
ofthesametypewhichcanbesolved
independently ofoneanother,followedby
recombiningthesub-solutions.
•Example:QuicksortisO(nlogn).
Perhapsnowisagoodtimeforareminderthatwhen
speakingasymptotically,thebaseoflogarithmsis
irrelevant. Thisisbecause oftheidentity
log
ablog
bn=logan.

21. Asymptotic Notation 21
ClassiΘcationofalgorithms-Θ(n
2
)
•Wecallthisclassquadratic.
•Asndoubles,run-timequadruples.
•However, itisstillpolynomial,whichweconsider
tobegood.
•Typicallyfoundwhere algorithmsdealwithall
pairsofdata.
•Example:
int *compute_sums(int A[], int n) {
int M[n][n];
int i,j;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
M[i][j]=A[i]+A[j];
return M;
}
•Moregenerally, ifanalgorithmisΘ(n
k
)for
constantkitiscalledapolynomial-time
algorithm.

22. Asymptotic Notation 22
ClassiΘcationofalgorithms-Θ(2
n
)
•Wecallthisclassexponential.
•Thisclassis,essentially,asbadasitgets.
•Algorithmsthatusebruteforce areofteninthis
class.
•Canbeusedonlyforsmallvaluesofninpractice.
•Example:Asimplewaytodetermine allnbit
numberswhosebinaryrepresentation hask
non-zero bitsistorunthroughallthenumbers
from1to2
n
,incrementingacounterwhena
numberhasknonzerobits. Itisclearthisis
exponential inn.

23. Asymptotic Notation 23
Comparisonofgrowthrates
logn nnlognn
2
n
3
2
n
0 1 0 1 1 2
0.6931 2 1.39 4 8 4
1.099 3 3.30 9 27 8
1.386 4 5.5516 64 16
1.609 5 8.0525125 32
1.792 610.7536216 64
1.946 713.6249343 128
2.079 816.6464512 256
2.197 919.7881729 512
2.303 1023.031001000 1024
2.398 1126.381211331 2048
2.485 1229.821441728 4096
2.565 1333.341692197 8192
2.639 1436.95196274416384
2.708 1540.62225337532768
2.773 1644.36256409665536
2.833 1748.162894913131072
2.890 1852.033245832262144
loglogmlogm m

24. Asymptotic Notation 24
Moregrowthrates
n100nn
2
11n
2
n
3
2
n
1100 1 11 1 2
2200 4 44 8 4
3300 9 99 27 8
440016176 64 16
550025275125 32
660036396216 64
770049539343 128
880064704512 256
990081891729 512
10100010011001000 1024
11110012113311331 2048
12120014415841728 4096
13130016918592197 8192
1414001962156274416384
1515002252475337532768
1616002562816409665536
17170028931794913131072
18180032435645832262144
19190036139716859524288

25. Asymptotic Notation 25
Moregrowthrates
n n
2
n
2
−nn
2
+99 n
3
n
3
+234
2 4 2 103 8 242
6 36 30 135 216 450
10100 90 199 1000 1234
14196 182 295 2744 2978
18324 306 423 5832 6066
22484 462 58310648 10882
26676 650 77517576 17810
30900 870 99927000 27234
341156 1122 125539304 39538
381444 1406 154354872 55106
421764 1722 186374088 74322
462116 2070 221597336 97570
502500 2450 2599125000 125234
542916 2862 3015157464 157698
583364 3306 3463195112 195346
623844 3782 3943238328 238562
664356 4290 4455287496 287730
704900 4830 4999343000 343234
745476 5402 5575405224 405458

26. Asymptotic Notation 26
0
5000
10000
15000
20000
25000
30000
35000
40000
0 5 10 15 20 25 30 35 40
Polynomial Functions
x
x**2
x**3
x**4

27. Asymptotic Notation 27
0
50
100
150
200
250
0 5 10 15 20 25 30 35 40
Slow Growing Functions
log(x)
x
x*log(x)
x**2

28. Asymptotic Notation 28
0
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
0 2 4 6 8 10
Fast Growing Functions Part 1
x
x**3
x**4
2**x

29. Asymptotic Notation 29
0
50000
100000
150000
200000
250000
300000
350000
400000
450000
500000
0 5 10 15 20
Fast Growing Functions Part 2
x
x**3
x**4
2**x

30. Asymptotic Notation 30
0
5e+07
1e+08
1.5e+08
2e+08
2.5e+08
3e+08
3.5e+08
4e+08
0 5 10 15 20 25 30
Why Constants and Non-Leading Terms Don’t Matter
1000000*x
300000*x**2 + 300*x
2**x

31. Asymptotic Notation 31
ClassiΘcationSummary
Wehaveseenthatwhenweanalyzefunctions
asymptotically:
•Onlytheleadingtermisimportant.
•Constantsdon'tmakeasigniΘcantdifference.
•Thefollowinginequalitiesholdasymptotically:
c <logn < log
2
n <
√
n < n < nlogn
n < nlogn < n
(1.1)
< n
2
< n
3
< n
4
<2
n
•Inotherwords,analgorithmthatisΘ(nlog(n))is
moreefΘcientthananalgorithmthatisΘ(n
3
).