Asymptotic Notation and Complexity

Complexity
Asymptotic Notation

Analysis of Algorithms
An algorithm is a finite set of precise instructions for
performing a computation or for solving a problem.
What is the goal of analysis of algorithms?
To compare algorithms mainly in terms of running time
but also in terms of other factors (e.g., memory
requirements, programmer's effort etc.)
What do we mean by running time analysis?
Determine how running time increases as the size
of the problem increases.
2

Input Size
Input size (number of elements in the input)
size of an array
# of elements in a matrix
# of bits in the binary representation of the input
vertices and edges in a graph
3

Types of Analysis
Worst case
Provides an upper bound on running time
An absolute guarantee that the algorithm would not run longer, no
matter what the inputs are
Best case
Provides a lower bound on running time
Input is the one for which the algorithm runs the fastest
Average case
Provides a prediction about the running time
Assumes that the input is random
4
Lower Bound RunningTime Upper Bound≤ ≤

Types of Analysis: Example
Example: Linear Search Complexity
Best Case : Item found at the beginning: One comparison
Worst Case : Item found at the end: n comparisons
Average Case :Item may be found at index 0, or 1, or 2, . . . or n - 1
Average number of comparisons is: (1 + 2 + . . . + n) / n = (n+1) / 2
 Worst and Average complexities of common sorting algorithms
5
Method Worst Case Average Case Best Case
Selection Sort n2
n2
n2
Insertion Sort n2
n2
n
Merge Sort nlogn nlogn nlogn
Quick Sort n2
nlogn nlogn

How do we compare algorithms?
We need to define a number of objective
measures.
(1) Compare execution times?
Not good: times are specific to a particular
computer !!
(2) Count the number of statements executed?
Not good: number of statements vary with the
programming language as well as the style of the
individual programmer.
6

Ideal Solution
Express running time as a function of the
input size n (i.e., f(n)).
Compare different functions corresponding
to running times.
Such an analysis is independent of
machine time, programming style, etc.
7

Example
Associate a "cost" with each statement.
Find the "total cost” by finding the total number of times
each statement is executed.
Algorithm 1 Algorithm 2
Cost Cost
arr[0] = 0; c1 for(i=0; i<N; i++) c2
arr[1] = 0; c1 arr[i] = 0; c1
arr[2] = 0; c1
... ...
arr[N-1] = 0; c1
----------- -------------
c1+c1+...+c1 = c1 x N (N+1) x c2 + N x c1 =
(c2 + c1) x N + c2
8

Another Example
Algorithm 3 Cost
sum = 0; c1
for(i=0; i<N; i++) c2
for(j=0; j<N; j++) c2
sum += arr[i][j]; c3
------------
c1 + c2 x (N+1) + c2 x N x (N+1) + c3 x N2
9

Asymptotic Analysis
To compare two algorithms with running
times f(n) and g(n), we need a rough
measure that characterizes how fast each
function grows.
Hint: use rate of growth
Compare functions in the limit, that is,
asymptotically!
(i.e., for large values of n)
10

Rate of Growth
Consider the example of buying elephants and
goldfish:
Cost: cost_of_elephants + cost_of_goldfish
Cost ~ cost_of_elephants (approximation)
The low order terms in a function are relatively
insignificant for large n
n4
+ 100n2
+ 10n + 50 ~ n4
i.e., we say that n4
+ 100n2
+ 10n + 50 and n4
have the
same rate of growth
11

Asymptotic Notation
 O notation: asymptotic “less than”:
 f(n)=O(g(n)) implies: f(n) “≤” g(n)
 Ω notation: asymptotic “greater than”:
 f(n)= Ω (g(n)) implies: f(n) “≥” g(n)
 Θ notation: asymptotic “equality”:
 f(n)= Θ (g(n)) implies: f(n) “=” g(n)
16

Big-O Notation
We say fA(n)=30n+8 is order n, or O (n)
It is, at most, roughly proportional to n.
fB(n)=n2
+1 is order n2
, or O(n2
). It is, at most,
roughly proportional to n2
.
In general, any O(n2
) function is faster- growing
than any O(n) function.
17

Visualizing Orders of Growth
On a graph, as
you go to the
right, a faster
growing
function
eventually
becomes
larger...
18
fA(n)=30n+8
Increasing n →
fB(n)=n2
+1
Valueoffunction→

More Examples …
n4
+ 100n2
+ 10n + 50 is O(n4
)
10n3
+ 2n2
is O(n3
)
n3
- n2
is O(n3
)
constants
10 is O(1)
1273 is O(1)
19

Back to Our Example
Algorithm 1 Algorithm 2
Cost Cost
arr[0] = 0; c1 for(i=0; i<N; i++) c2
arr[1] = 0; c1 arr[i] = 0; c1
arr[2] = 0; c1
...
arr[N-1] = 0; c1
----------- -------------
c1+c1+...+c1 = c1 x N (N+1) x c2 + N x c1 =
(c2 + c1) x N + c2
Both algorithms are of the same order: O(N)
20

Example (cont’d)
Algorithm 3 Cost
sum = 0; c1
for(i=0; i<N; i++) c2
for(j=0; j<N; j++) c2
sum += arr[i][j]; c3
------------
c1 + c2 x (N+1) + c2 x N x (N+1) + c3 x N2
= O(N2
)
21

Asymptotic notations
O-notation
22

Big-O Visualization
23
O(g(n)) is the set of
functions with smaller
or same order of
growth as g(n)

Examples
2n2
= O(n3
):
 n2
= O(n2
):
 1000n2
+1000n = O(n2
):
 n = O(n2
):
24
2n2
≤ cn3
⇒ 2 ≤ cn ⇒ c = 1 and n0= 2
n2
≤ cn2
⇒ c ≥ 1 ⇒ c = 1 and n0= 1
1000n2
+1000n ≤ 1000n2
+ n2
=1001n2
⇒ c=1001 and n0 = 1000
n ≤ cn2
⇒ cn ≥ 1 ⇒ c = 1 and n0= 1

More Examples
Show that 30n+8 is O(n).
Show ∃c,n0: 30n+8 ≤ cn, ∀n>n0 .
Let c=31, n0=8. Assume n>n0=8. Then
cn = 31n = 30n + n > 30n+8, so 30n+8 < cn.
25

Big-O example, graphically
Note 30n+8 isn’t
less than n
anywhere (n>0).
It isn’t even
less than 31n
everywhere.
But it is less than
31n everywhere to
the right of n=8.
26
n>n0=8 →
Increasing n →
Valueoffunction→
n
30n+8
cn =
31n
30n+8
∈O(n)

No Uniqueness
There is no unique set of values for n0 and c in proving the
asymptotic bounds
Prove that 100n + 5 = O(n2
)
 100n + 5 ≤ 100n + n = 101n ≤ 101n2
for all n ≥ 5
n0 = 5 and c = 101 is a solution
 100n + 5 ≤ 100n + 5n = 105n ≤ 105n2
for all n ≥ 1
n0 = 1 and c = 105 is also a solution
Must find SOME constants c and n0 that satisfy the asymptotic notation relation
27

Asymptotic notations (cont.)
Ω - notation
28
Ω(g(n)) is the set of functions
with larger or same order of
growth as g(n)

Examples
 5n2
= Ω(n)
100n + 5 ≠ Ω(n2
)
n = Ω(2n), n3
= Ω(n2
), n = Ω(logn)
29
∃ c, n0 such that: 0 ≤ cn ≤ 5n2 ⇒ cn ≤ 5n2
⇒ c = 1 and n0 = 1
∃ c, n0 such that: 0 ≤ cn2
≤ 100n + 5
100n + 5 ≤ 100n + 5n (∀ n ≥ 1) = 105n
cn2
≤ 105n ⇒ n(cn – 105) ≤ 0
Since n is positive ⇒ cn – 105 ≤ 0 ⇒ n ≤ 105/c
⇒ contradiction: n cannot be smaller than a constant

Asymptotic notations (cont.)
30
Θ-notation
Θ(g(n)) is the set of functions
with the same order of growth
as g(n)

Examples
n2
/2 –n/2 = Θ(n2
)
 ½ n2
- ½ n ≤ ½ n2
∀n ≥ 0 ⇒ c2= ½
 ½ n2
- ½ n ≥ ½ n2
- ½ n * ½ n ( ∀n ≥ 2 ) = ¼ n2
⇒ c1=
¼
n ≠ Θ(n2
): c1 n2
≤ n ≤ c2 n2
⇒ only holds for: n ≤ 1/c1
31

Examples
6n3
≠ Θ(n2
): c1 n2
≤ 6n3
≤ c2 n2
⇒ only holds for: n ≤ c2 /6
n ≠ Θ(logn): c1 logn ≤ n ≤ c2 logn
⇒ c2 ≥ n/logn, ∀ n≥ n0 – impossible
32

Relations Between Different Sets
Subset relations between order-of-growth sets.
33
R→R
Ω( f )O( f )
Θ( f )
• f

Logarithms and properties
In algorithm analysis we often use the notation “log n”
without specifying the base
nn
nn
elogln
loglg 2
=
= =y
xlog
34
Binary logarithm
Natural logarithm
)lg(lglglg
)(lglg
nn
nn kk
=
=
xy log
=xylog yx loglog +
=
y
x
log yx loglog −
logb x =
ab
xlog
=xb
alog
log
log
a
a
x
b

More Examples
For each of the following pairs of functions, either f(n) is
O(g(n)), f(n) is Ω(g(n)), or f(n) = Θ(g(n)). Determine
which relationship is correct.
f(n) = log n2
; g(n) = log n + 5
f(n) = n; g(n) = log n2
f(n) = log log n; g(n) = log n
f(n) = n; g(n) = log2
n
f(n) = n log n + n; g(n) = log n
f(n) = 10; g(n) = log 10
f(n) = 2n
; g(n) = 10n2
f(n) = 2n
; g(n) = 3n
35
f(n) = Θ (g(n))
f(n) = Ω(g(n))
f(n) = O(g(n))
f(n) = Ω(g(n))
f(n) = Ω(g(n))
f(n) = Θ(g(n))
f(n) = Ω(g(n))
f(n) = O(g(n))

Properties
Theorem:
f(n) = Θ(g(n)) ⇔ f = O(g(n)) and f = Ω(g(n))
Transitivity:
 f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n))
 Same for O and Ω
Reflexivity:
 f(n) = Θ(f(n))
 Same for O and Ω
Symmetry:
 f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n))
Transpose symmetry:
 f(n) = O(g(n)) if and only if g(n) = Ω(f(n))
36

Summary
Algorithm
Complexity
Best, Average and Worst Case Complexity
Asymptotic Notation
Big – Oh
Big – Omega
Big – Theta
37

Asymptotic Notation and Complexity

Recommended

More Related Content

What's hot (20)

Similar to Asymptotic Notation and Complexity (20)

More from Rajandeep Gill (7)

Recently uploaded (20)

Asymptotic Notation and Complexity