, Lesson 1
Warst case
complexity : T(n) = mai
[t() x-In] :
Best
complexity
case : T(n) = min Gt(x) : -In]
Average case
complexity T(n) =
[ p(x)t(x)
xtIn
p(x) =
probability of having as input
If all instance have the same
probability and In is finite :
1
T(n) [xtInt(x)
p(x) = and =
lIn) /In/
total time 2 + 2ck
2 if the element is inthe sequence
Element not found : T(x) =
2n + 2
length of the sequence
↳
n =
Element found at last position :
T(x) =
2 + 2cn + 2 = 4+ 2
Wast case : 22h + 4
Best case (elemt first position) : T(n) =
4c + 2c = 6
Average : T(n) =
14 + 2k) = (2 k) +
= (2) = (2nn
= cn + 5n
Growth
Order
of
Big -O rotation
O(f(n)) =
(g(n) : 7 no ,o such that
g(n) < (f(n) for n, no]
Big-1 rotation (f(n) =
(g(n) : -no , o such that
g(n) (f(n) for
,
nc, no]
Big-O rotation O(f(n)) =
[g(n) g(n) 0(f(n)
: = and
g(n) =
r(t(n))]
·
n =
0(n(2) g(n) =
nf(n) = 4/2
g(n) = c .
f(n)c =
2 no 1 =
·
100n2 + n =0(n') g(n) = 100n2+ n f(n) = n
< c f(n) en
g(n) .
= 100m2 + n c= 101 no =
1
zn + 2 0(n3) +r 2
f(n) 3
·
=
g(n) = + =
f(n) 7n3 n2 c
g(n) = c .
= + = c= 8 no = 1
N100 e(n)
g(n) 4,00 f(n) c 1/100
= =
f(n) = n
g(nic , c .
=
no = 1
,If f = O (F(n)) and
g = 0(f(n)) then :
f g + =
0(maxF(n) G(n) ,
O (F(n)) + =(f(n)) = 0(max F(n) , G(n)
>
- Also
apply for 2 0 0
Complexity vs Time
T(n) 1 min for 1000
= n
inputs
T(n) =
log n - 0, 65
T(n) =
nlogn 310 min
T(n) = n2 = 16h
T(n) = n3 -
694 days
T(n) = 2" -infinite
Order
of Growth slowest -
fastest
n ch
1 ,
logn logn , ,
En ,
n
,
nogn , ,
Equations
n+
f(n) n + 0(1)
g(n) 0(1) f(n) g(n)
·
= = =
= +
, TD1
1 Cret 2 Efficient
*
Alg . .
anank Ck
order : constant <
log <linear <
nlog(n) <
O ⑦
Big Big
1 Wast Best Average
r(g(n)
.
2
. Upper lower & Tight >
- O(g(n)
3 . 0x f(n) => c .
g(n) f(n)c ,
c .
g(n) Cg(n) = f(n) = Gf(n)
f(n) =
0(g(n)
.im
4 = 0
lim
n- p
=
clim- = (s)
constant 1 statement
logarithmic logn divide in
half
linear N loop
livarithmic Nlogn divide and conquer
quadratic N2 double loop
cubic N3 tiple loop
2N
exponential exhalutive search
f(n) Fn no
Big-0 :
g(n)
= c .
,
Big-1 :
f(nk g(n) Enc no
,
c .
,
Big-0 :
(g(n)[f(n) = g(n) Enc , no
logi slogan nan'logn <n22" in !
Warst case
complexity : T(n) = mai
[t() x-In] :
Best
complexity
case : T(n) = min Gt(x) : -In]
Average case
complexity T(n) =
[ p(x)t(x)
xtIn
p(x) =
probability of having as input
If all instance have the same
probability and In is finite :
1
T(n) [xtInt(x)
p(x) = and =
lIn) /In/
total time 2 + 2ck
2 if the element is inthe sequence
Element not found : T(x) =
2n + 2
length of the sequence
↳
n =
Element found at last position :
T(x) =
2 + 2cn + 2 = 4+ 2
Wast case : 22h + 4
Best case (elemt first position) : T(n) =
4c + 2c = 6
Average : T(n) =
14 + 2k) = (2 k) +
= (2) = (2nn
= cn + 5n
Growth
Order
of
Big -O rotation
O(f(n)) =
(g(n) : 7 no ,o such that
g(n) < (f(n) for n, no]
Big-1 rotation (f(n) =
(g(n) : -no , o such that
g(n) (f(n) for
,
nc, no]
Big-O rotation O(f(n)) =
[g(n) g(n) 0(f(n)
: = and
g(n) =
r(t(n))]
·
n =
0(n(2) g(n) =
nf(n) = 4/2
g(n) = c .
f(n)c =
2 no 1 =
·
100n2 + n =0(n') g(n) = 100n2+ n f(n) = n
< c f(n) en
g(n) .
= 100m2 + n c= 101 no =
1
zn + 2 0(n3) +r 2
f(n) 3
·
=
g(n) = + =
f(n) 7n3 n2 c
g(n) = c .
= + = c= 8 no = 1
N100 e(n)
g(n) 4,00 f(n) c 1/100
= =
f(n) = n
g(nic , c .
=
no = 1
,If f = O (F(n)) and
g = 0(f(n)) then :
f g + =
0(maxF(n) G(n) ,
O (F(n)) + =(f(n)) = 0(max F(n) , G(n)
>
- Also
apply for 2 0 0
Complexity vs Time
T(n) 1 min for 1000
= n
inputs
T(n) =
log n - 0, 65
T(n) =
nlogn 310 min
T(n) = n2 = 16h
T(n) = n3 -
694 days
T(n) = 2" -infinite
Order
of Growth slowest -
fastest
n ch
1 ,
logn logn , ,
En ,
n
,
nogn , ,
Equations
n+
f(n) n + 0(1)
g(n) 0(1) f(n) g(n)
·
= = =
= +
, TD1
1 Cret 2 Efficient
*
Alg . .
anank Ck
order : constant <
log <linear <
nlog(n) <
O ⑦
Big Big
1 Wast Best Average
r(g(n)
.
2
. Upper lower & Tight >
- O(g(n)
3 . 0x f(n) => c .
g(n) f(n)c ,
c .
g(n) Cg(n) = f(n) = Gf(n)
f(n) =
0(g(n)
.im
4 = 0
lim
n- p
=
clim- = (s)
constant 1 statement
logarithmic logn divide in
half
linear N loop
livarithmic Nlogn divide and conquer
quadratic N2 double loop
cubic N3 tiple loop
2N
exponential exhalutive search
f(n) Fn no
Big-0 :
g(n)
= c .
,
Big-1 :
f(nk g(n) Enc no
,
c .
,
Big-0 :
(g(n)[f(n) = g(n) Enc , no
logi slogan nan'logn <n22" in !
