Chapter 2 Computational Complexity Chapter 2 Computational Complexity Notes | EduRev

: Chapter 2 Computational Complexity Chapter 2 Computational Complexity Notes | EduRev

 Page 1


Chapter 2 
Computational Complexity 
 
Page 2


Chapter 2 
Computational Complexity 
 
Computational Complexity 
?Compares growth of two functions 
?Independent of constant multipliers and 
lower-order effects 
?Metrics 
?“Big O” Notation O() 
?“Big Omega” Notation ?() 
?“Big Theta” Notation T() 
Page 3


Chapter 2 
Computational Complexity 
 
Computational Complexity 
?Compares growth of two functions 
?Independent of constant multipliers and 
lower-order effects 
?Metrics 
?“Big O” Notation O() 
?“Big Omega” Notation ?() 
?“Big Theta” Notation T() 
Big “O” Notation 
? f(n) =O(g(n))  
? If and only if  
there exist two constants c > 0  and n
0
 > 0,  
such that f(n) = cg(n)  for all n = n
0
 
? iff   ? c, n
0
 > 0   s.t. ? n = n
0 
: 0 = f(n) = cg(n) 
n
0 
f(n) 
cg(n) 
f(n) is eventually 
upper- 
bounded by g(n) 
Page 4


Chapter 2 
Computational Complexity 
 
Computational Complexity 
?Compares growth of two functions 
?Independent of constant multipliers and 
lower-order effects 
?Metrics 
?“Big O” Notation O() 
?“Big Omega” Notation ?() 
?“Big Theta” Notation T() 
Big “O” Notation 
? f(n) =O(g(n))  
? If and only if  
there exist two constants c > 0  and n
0
 > 0,  
such that f(n) = cg(n)  for all n = n
0
 
? iff   ? c, n
0
 > 0   s.t. ? n = n
0 
: 0 = f(n) = cg(n) 
n
0 
f(n) 
cg(n) 
f(n) is eventually 
upper- 
bounded by g(n) 
Big “Omega” Notation 
? f(n) = ?(g(n)) 
?iff   ? c, n
0
 > 0  s.t. ? n = n0 , 0 = cg(n) = f(n) 
f(n) 
cg(n) 
n
0 
f(n) is eventually 
lower-bounded by g(n) 
Page 5


Chapter 2 
Computational Complexity 
 
Computational Complexity 
?Compares growth of two functions 
?Independent of constant multipliers and 
lower-order effects 
?Metrics 
?“Big O” Notation O() 
?“Big Omega” Notation ?() 
?“Big Theta” Notation T() 
Big “O” Notation 
? f(n) =O(g(n))  
? If and only if  
there exist two constants c > 0  and n
0
 > 0,  
such that f(n) = cg(n)  for all n = n
0
 
? iff   ? c, n
0
 > 0   s.t. ? n = n
0 
: 0 = f(n) = cg(n) 
n
0 
f(n) 
cg(n) 
f(n) is eventually 
upper- 
bounded by g(n) 
Big “Omega” Notation 
? f(n) = ?(g(n)) 
?iff   ? c, n
0
 > 0  s.t. ? n = n0 , 0 = cg(n) = f(n) 
f(n) 
cg(n) 
n
0 
f(n) is eventually 
lower-bounded by g(n) 
Big “Theta” Notation 
? f(n) = T(g(n)) 
 
? iff ? c
1
, c
2
, n
0
 > 0  s.t.  0 = c
1
g(n) = f(n) = c
2
g(n),  ? n >= n
0
 
f(n) 
c
1
g(n) 
n
0 
c
2
g(n) 
f(n) has the  
same long-term  
rate of  
growth as g(n) 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!