Algorithm -
a
finite set
of
well-defined instructions for accomplishing
Insertion sort
pseudocode :
complexity :
Z
T ( )
n n n
Loop Invariants
-
an invariant must hold true
times
at all
during a loop exec
-
.
Initialization Maintenance Termination
, .
(before base case)
, (while ,
inductive step) (after result)
,
,Running Time Cars model )
aaffem.ws least of ) statement ×
(mwsbfdahhttifeuu.ae )
-
line i takes constant time Ci
-
when a fool while loop exits
normally ,
the test is executed one more time than loop body
Average case
complexity can be
asymptotically
as bad as worst case
0 ( n) -
Big
-
O notation -
asymptotic
upper bound
of complexity
, R ( n) -
Big Omega
-
notation
-
asymptotic lower bound of complexity
! flu ) =
Algin) ) gcu)
=
Off Cn))
O ( n) notation
Big Theta
- -
-
asymptotic right bound
of complexity
= both upper bound and lower bound
f- = O
(g) means F ca
, ca C- Rt :
glu) flu ) Cag ( n )
2-
Ca E
=
f- and
g
are same order of magnitude
Examples :
Binary search -
O (log ) n
linear search
-
O ( u)
Quick sort -
O ( n Wgn)
Insertion Sort -
O ( u2 )
a
finite set
of
well-defined instructions for accomplishing
Insertion sort
pseudocode :
complexity :
Z
T ( )
n n n
Loop Invariants
-
an invariant must hold true
times
at all
during a loop exec
-
.
Initialization Maintenance Termination
, .
(before base case)
, (while ,
inductive step) (after result)
,
,Running Time Cars model )
aaffem.ws least of ) statement ×
(mwsbfdahhttifeuu.ae )
-
line i takes constant time Ci
-
when a fool while loop exits
normally ,
the test is executed one more time than loop body
Average case
complexity can be
asymptotically
as bad as worst case
0 ( n) -
Big
-
O notation -
asymptotic
upper bound
of complexity
, R ( n) -
Big Omega
-
notation
-
asymptotic lower bound of complexity
! flu ) =
Algin) ) gcu)
=
Off Cn))
O ( n) notation
Big Theta
- -
-
asymptotic right bound
of complexity
= both upper bound and lower bound
f- = O
(g) means F ca
, ca C- Rt :
glu) flu ) Cag ( n )
2-
Ca E
=
f- and
g
are same order of magnitude
Examples :
Binary search -
O (log ) n
linear search
-
O ( u)
Quick sort -
O ( n Wgn)
Insertion Sort -
O ( u2 )
