Courses

# 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)
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!