Introduction to Algorithms

Lecture# 02: Asymptotic Notations and Analysis

1
Asymptotic Notations Properties
• Categorize algorithms based on asymptotic growth rate
• e.g. linear, quadratic, exponential

• Ignore small constant and small inputs

• Estimate upper bound and lower bound on growth rate of time

complexity function

• Describe running time of algorithm as n grows to .

Limitations
• not always useful for analysis on fixed-size inputs.
2
• All results are for sufficiently large inputs.
Asymptotic Notations
Asymptotic Notations , O, , o, 
 We use  to mean “order exactly”, (Tight Bound)
 O to mean “order at most”, (Tight Upper Bound)
  to mean “order at least”, (Tight Lower Bound)
 o to mean “upper bound”,
•  to mean “lower bound”,

Define a set of functions which is in practice used to compare

two function sizes.

3
Big-Oh Notation (O)
If f, g: N  R+, then we can define Big-Oh as
For a given function g n   0, denoted by g n  the set of functions,
g n    f n  : there exist positive constants c and no such that
0  f n   cg n , for all n  n o 
f n   g n  means function g n  is an asymptotic ally
upper bound for f n .

We may write f(n) = O(g(n)) OR f(n)  O(g(n))

Intuitively:
Set of all functions whose rate of growth is the same as or lower than
that of g(n). f(n) is bounded above by g(n) for all sufficiently large n 4
Big-Oh Notation (O)

f(n)  O(g(n))

 c > 0,  n0 > 0 and n  n0, 0  f(n)  c.g(n)

5
g(n) is an asymptotic upper bound for f(n).
Big-Oh Notation (O)
The idea behind the big-O notation is to establish an upper boundary
for the growth of a function f(n) for large n.

This boundary is specified by a function g(n) that is usually much

simpler than f(n).

We accept the constant C in the requirement

f(n)  Cg(n) whenever n > n0,

We are only interested in large n, so it is OK if

f(n) > Cg(n) for n  n0.

The relationship between f and g can be expressed by stating either

that g(n) is an upper bound on the value of f(n) or that in the long run , 6
f grows at most as fast as g.
Example
• As a simple illustrative example, we show that the function
2n2 + 5n + 6 is O(n2).

• For all n ≥ 1, it is the case that

2n2 + 5n + 6 ≤ 2n2 + 5n2 + 6n2 = 13n2

• Hence, we can take с = 13 and no =1, and the definition is

satisfied.

7
Example
Prove that 2n2 = O(n3)

Proof:
Assume that f(n) = 2n2, and g(n) = n3
f(n) = O(g(n)) ?

Now we have to find the existence of c and n 0

f(n) ≤ c.g(n)  2n2 ≤ c.n3  2 ≤ c.n

if we take, c = 1 and n0= 2 OR

c = 2 and n0= 1 then
8
2n ≤ c.n
2 3

Hence f(n) = O(g(n)), c = 1 and n0= 2

Example
Prove that n2 = O(n2)

Proof:
Assume that f(n) = n2, and g(n) = n2
f(n) = O(g(n)) ?
Now we have to find the existence of c and n 0

f(n) ≤ c.g(n)  n2 ≤ c.n2  1 ≤ c

if we take, c = 1, n0= 1
Then
n2 ≤ c.n2 for c = 1 and n  1
9
Hence, n2 = O(n2), where c = 1 and n0= 1
Example
Prove that 1000.n2 + 1000.n = O(n2)

Proof:
Assume that f(n) = 1000.n2 + 1000.n, and g(n) = n2
We have to find existence of c and n 0 such that
0 ≤ f(n) ≤ c.g(n) for all n  n0

1000.n2 + 1000.n ≤ c.n2

for c = 1001, 1000.n2 + 1000.n ≤ 1001.n2
1000.n ≤ n2  n2 - 1000.n  0
n (n-1000)  0,

this true for n  1000

10

Hence f(n) = O(g(n)) for c = 1001 and n0 = 1000

Example
Disprove that n3 ≠ O(n2)

Proof:
On contrary we assume that there exist some positive constants
c and n0 such that
0 ≤ n3 ≤ c.n2 for all n  n0
n≤c

Since c is any fixed number and n is any arbitrary constant,

therefore n ≤ c is not possible in general.

Hence our supposition is wrong and n3 ≤ c.n2, for n  n0 is not

true for any combination of c and n0.
Hence, n3 ≠ O(n2) 11
Example
Prove that 2n + 10 = O(n)

Proof:
Assume that f(n) = 2n + 10, and g(n) = n
f(n) = O(g(n)) ?
Now we have to find the existence of c and n 0

f(n) ≤ c.g(n)  2n + 10 ≤ c.n  (c  2) n  10  n  10/(c  2)

c > 2 for n >0, we pick, c = 3, then n 0= 10

Then
2n + 10 ≤ c.n for c = 3 and n  10
12
Hence, 2n + 10 = O(n), where c = 3 and n0= 10
Example
Prove which of the following function is larger by order of growth?
(1/3)n or 17?

• Let’s check if
(1/3)n = O( 17)
(1/3)n ≤ c.17, which is true for c=1,n0 = 1
• Let’s check if
17 = O((1/3)n )
17 ≤ c. (1/3)n , which is true for c > 17. 3n
• And hence can’t be bounded for large n.
• That’s why (1/3)n is less in growth rate then 17.

13
Example
Prove or disprove 22n = O(2n )?

• To prove above argument we have to show

• 22n ≤ C . 2n
• 2n 2n ≤ C .2n

• This inequality holds only when

• C ≥ 2n
• which makes C to be non-constant.

• Hence we can’t bound 22n by O(2n)

14
Example
Prove that : 8n2 + 2n - 3 = O(n2)

Proof:
Need c > 0 and n0  1 such that
8n2 + 2n - 3 ≤ c.n2 for n  n0

Consider the reasoning:

f(n) = 8n2 + 2n - 3 ≤ 8n2 + 2n ≤ 8n2 + 2n2 = 10n2

Hence, 8n2 + 2n - 3 = O(n2), where c = 10 and n0= 1

15
Example
Can you bound 3n = O(2n ) ?

To prove above argument we have to show

3n ≤ C. 2n
3n ≤ C. 2n
3n ≤ (3/2)n 2n
This inequality holds only when C ≥ (3/2)n, which makes C to be non-
constant.

Hence we can’t bound 3n by O(2n)

16
Example
Which of the following function is larger by order of growth? N log N
or N1.5?

Note that g(N) = N 1.5 = N•N 0.5

Hence, between f(N) and g(N), we only need to compare growth
rate of log(N) and N 0.5

Equivalently, we can compare growth rate of log2N with N

Now, we can refer to the previously state result to figure out whether
f(N) or g(N) grows faster!

17
Big-Omega Notation ()
If f, g: N  R+, then we can define Big-Omega as

For a given function g n  denote by g n  the set of functions,

g n    f n  : there exist positive constants c and no such that
0  cg n   f n  for all n n o 
f n   g n , means that function g n  is an asymptotically
lower bound for f n .

We may write f(n) = (g(n)) OR f(n)  (g(n))

Intuitively:
Set of all functions whose rate of growth is the same as or higher than
that of g(n).
18
Big-Omega Notation ()

f(n)  (g(n))

 c > 0,  n0 > 0 , n  n0, f(n)  c.g(n)

g(n) is an asymptotically lower bound for f(n).
19
Note the duality rule: t(n)(f(n))  f(n)O(t(n))
Example
Prove that 3n + 2 = (n)

Proof:
Assume that f(n) = 3n + 2 , and g(n) = n
f(n) = (g(n)) ?

We have to find the existence of c and n0 such that

c.g(n) ≤ f(n) for all n  n0
c.n ≤ 3n + 2

At R.H.S a positive term is being added to 3n, which will make L.H.S ≤
R.H.S for all values of n, when c = 3.

Hence f(n) = (g(n)), for c = 3 and n0= 1 20

Example
Prove that 5.n2 = (n)

Proof:
Assume that f(n) = 5.n2 , and g(n) = n
f(n) = (g(n)) ?

We have to find the existence of c and n0 such that

c.g(n) ≤ f(n) for all n  n0
c.n ≤ 5.n2  c ≤ 5.n

if we take, c = 5 and n0= 1 then

c.n ≤ 5.n2 for all n  n0

Hence f(n) = (g(n)), for c = 5 and n0= 1 21

Example
Prove that 5n2 + 2n - 3 = (n2)

Proof:
Assume that f(n) = 5n2 + 2n - 3, and g(n) = n2
f(n) = (g(n)) ?

We have to find the existence of c and n0 such that

c.g(n) ≤ f(n) for all n  n0
c.n2 ≤ 5.n2 + 2n - 3

We can take c = 5, given that 2n-3 is always positive.

2n-3 is always positive for n  2. Therefore n0 = 2.

And hence f(n) = (g(n)), for c = 5 and n0= 2

22
Example
Prove that 100.n + 5 = (n2)

Proof:
Let f(n) = 100.n + 5, and g(n) = n2
Assume that f(n) = (g(n)) ?

Now if f(n) = (g(n)) then there exist c and n0 such that

c.g(n) ≤ f(n) for all n  n0
c.n2 ≤ 100.n + 5
f n 
For the above inequality to hold nlim
 g n 
 meaning f(n)
grows faster than g(n).
100n  5
But nlim 2
0 which means g(n) is growing faster than
 n 23
f(n)

And hence f(n) ≠ (g(n))

Theta Notation ()
If f, g: N  R+, then we can define Big-Theta as

For a given function g n  denoted by g n  the set of functions,

g n    f n  : there exist positive constants c1 , c2 and no such that
0  c1 g n   f n   c2 g n  for all n  n o 
f n   g n  means function f n  is equal to g n  to within a constant
factor, and g n  is an asymptotic ally tight bound for f n .

We may write f(n) = (g(n)) OR f(n)  (g(n))

Intuitively: Set of all functions that have same rate of growth as g(n).
When a problem is (n), this represents both an upper and lower
bound i.e. it is O(n) and (n) (no algorithmic gap) 24
Theta Notation ()

f(n)  (g(n))

 c1> 0, c2> 0,  n0 > 0,  n  n0, c2.g(n)  f(n)  c1.g(n)

25
We say that g(n) is an asymptotically tight bound for f(n).
Example
Prove that ½.n2 – ½.n = (n2)

Proof:
Assume that f(n) = ½.n2 – ½.n, and g(n) = n2
f(n) = (g(n))?
We have to find the existence of c 1, c2 and n0 such that
c1.g(n) ≤ f(n) ≤ c2.g(n) for all n  n0

Since, ½ n2 - ½ n ≤ ½ n2 then c2= ½ ,n ≥ 0 and

Since ½ n is subtracted from ½ n2 , c1 must be less than ½,
Assuming c1= ¼  ¼ n2 ≤ ½ n2 - ½ n  n ≥ 2
26
c1.g(n) ≤ f(n) ≤ c2.g(n) n ≥ 2, c1= ¼, c2 = ½
Hence f(n) = (g(n))  ½.n2 – ½.n = (n2)
Example
Prove that 2.n2 + 3.n + 6 ≠ (n3)

Proof: Let f(n) = 2.n2 + 3.n + 6, and g(n) = n3

we have to show that f(n) ≠ (g(n))
On contrary assume that f(n)  (g(n)) i.e. there exist some
positive constants c1, c2 and n0 such that:
c1.g(n) ≤ f(n) ≤ c2.g(n)
Solve for c2:
f(n) ≤ c2.g(n)  2n2 + 3n + 6 ≤ 2n2 + 3n2 + 6n2 ≤ c2n3  c = 11 and n0= 1
Solve for c1:
c1.g(n) ≤ f(n)  c1n3 ≤ 2n2 + 3n + 6  c1n3 ≤ 2n2 ≤ 2n2 + 3n + 6
c1.n ≤ 2, for large n this is not possible 27

Hence f(n) ≠ (g(n))  2.n2 + 3.n + 6 ≠ (n3)

Example from the book
Prove that ½.n2 – 3.n = (n2)

Proof
Let f(n) = ½.n2 – 3.n, and g(n) = n2 f(n) = (g(n))?
We have to find the existence of c 1, c2 and n0 such that
c1.g(n) ≤ f(n) ≤ c2.g(n)  n  n0
c1. n2 ≤ ½.n2 – 3.n ≤ c2. n2

Since, ½ n2 - 3 n ≤ ½ n2 n ≥ 1 if c2= ½ and

½ n2 - 3 n ≥ 1/4 n2 ( n ≥ 6 ), c1= ¼

c1.g(n) ≤ f(n) ≤ c2.g(n) n ≥ 6, c1= ¼, c2 = ½ 28

Hence f(n) = (g(n))  ½.n2 – 3.n = (n2)
Little-Oh Notation
o-notation is used to denote a upper bound that is not
asymptotically tight.

For a given function g n   0, denoted by og n  the set of functions,

 f n  : for any positive constants c, there exists a constant no
og n   
such that 0  f n   cg n  for all n  n o 

f(n) becomes insignificant relative to g(n) as n approaches

infinity. g(n) is an upper bound for f(n), not asymptotically tight

f n 
 
e.g., 2n  o n but 2n  o n ..
2 2
 2 lim
n  g n 
0
29
Example
Prove that 2n2 = o(n3)

Proof:
Assume that f(n) = 2n2 , and g(n) = n3
f(n) = o(g(n)) ?

Now we have to find the existence n0 for any c

f(n) < c.g(n) this is true
2n2 < c.n3  2 < c.n

This is true for any c, because for any arbitrary c we can

choose n0 such that the above inequality holds.

Hence f(n) = o(g(n))

30
Example
Prove that n2 ≠ o(n2)

Proof:
Assume that f(n) = n2 , and g(n) = n2
Now we have to show that f(n) ≠ o(g(n))

Since
f(n) < c.g(n)  n2 < c.n2  1 ≤ c,

In our definition of small o, it was required to prove for any c

but here there is a constraint over c .

Hence, n2 ≠ o(n2), where c = 1 and n0= 1

31
Little-Omega Notation
Little- notation is used to denote a lower bound that is not
asymptotically tight.

For a given function g n , denote by  g n  the set of all functions.

 g n    f n  : for any positive constants c, there exists a constant no such that
0  cg n   f n  for all n  n o 

f(n) becomes arbitrarily large relative to g(n) as n

approaches infinity

f n 
  n 2 ..
n2 n2
e.g.,   n  but lim
n  g n 

2 2
32
Example
Prove that 5.n2 = (n)

Proof:
Assume that f(n) = 5.n2 , and g(n) = n
f(n) = (g(n)) ?

We have to prove that for any c there exists n 0 such that

c.g(n) < f(n) for all n  n0

c.n < 5.n2  c < 5.n

This is true for any c, because for any arbitrary c e.g. c =

1000000, we can choose n0 = 1000000/5 = 200000 and the
above inequality does hold. 33

And hence f(n) = (g(n))

Example
Prove that 5.n + 10 ≠ (n)

Proof:
Assume that f(n) = 5.n + 10, and g(n) = n
f(n) ≠ (g(n)) ?

We have to find the existence n0 for any c, such that

c.g(n) < f(n) for all n  n0

c.n < 5.n + 10, if we take c = 16 then

16.n < 5.n + 10  11.n < 10 is not true for any positive integer.

Hence f(n) ≠ (g(n))

34
Example
Prove that 100.n ≠ (n2)

Proof:
Let f(n) = 100.n, and g(n) = n2
Assume that f(n) = (g(n))
Now if f(n) = (g(n)) then there n0 for any c such that
c.g(n) < f(n) for all n  n0

c.n2 < 100.n  c.n < 100

If we take c = 100, n < 1, not possible

Hence f(n) ≠ (g(n)) i.e. 100.n ≠ (n2)

35
Asymptotic Functions Summary
If f(n) = (g(n)) we say that f(n) and g(n) grow at the same rate,
asymptotically

If f(n) = O(g(n)) and f(n) ≠ (g(n)), then we say that f(n) is asymptotically
slower growing than g(n).

If f(n) = (g(n)) and f(n) ≠ O(g(n)), then we say that f(n) is asymptotically
faster growing than g(n).

36
Usefulness of Notations
It is not always possible to determine behaviour of an algorithm
using  -notation.

For example, given a problem with n inputs, we may have an

algorithm to solve it in a.n2 time when n is even and c.n time when n
is odd. OR

We may prove that an algorithm never uses more than e.n2 time
and never less than f.n time.

In either case we can neither claim (n) nor (n2) to be the order of
the time usage of the algorithm.
37
Big O and  notation will allow us to give at least partial information
Usefulness of Notations
To express the efficiency of our algorithms which of the three
notations should we use?

As computer scientist we generally like to express our algorithms as

big O since we would like to know the upper bounds of our
algorithms.

Why?
If we know the worse case then we can aim to improve it and/or
avoid it.

38
Usefulness of Notations
Even though it is correct to say “7n - 3 is O(n3)”, a better statement is
“7n - 3 is O(n)”, that is, one should make the approximation as tight as
possible

Simple Rule:
Drop lower order terms and constant factors
7n-3 is O(n)
8n2log n + 5n2 + n is O(n2log n)

Strictly speaking this use of the equals sign is incorrect

• the relationship is a set inclusion, not an equality
• f(n)  O(g(n)) is better
39
Big Oh Does Not Tell the Whole Story
Question?
• If two algorithms A and B have the same asymptotic complexity, say
O(n2), will the execution time of the two algorithms always be
same?
• How to select between the two algorithms having the same
asymptotic performance?

Answer:
• They may not be the same. There is this small matter of the
constant of proportionality.
• Suppose that A does ten operations for each data item, but
algorithm B only does three.
• It is reasonable to expect B to be faster than A even though both 40
have the same asymptotic performance. The reason is that
asymptotic analysis ignores constants of proportionality.
Big Oh Does Not Tell the Whole Story
Algorithm_A {
set up the algorithm; /*taking 50 time units*/
read in n elements into array A; /* 3 units per element */
for (i = 0; i < n; i++) {
do operation1 on A[i]; /* takes 10 units */
do operation2 on A[i]; /* takes 5 units */
do operation3 on A[i]; /* takes 15 units */
} TA(n) = 50 + 3n + (10 + 5 + 15)*n
} = 50 + 33*n

Algorithm_B {
set up the algorithm; /*taking 200 time units*/
read in n elements into array A; /* 3 units per element */
for (i = 0; i < n; i++) {
do operation1 on A[i]; /* takes 10 units */
do operation2 on A[i]; /* takes 5 units */ 41
} TB(n) = 200 + 3n + (10 + 5)*n
} = 200 + 18*n
Big Oh Does Not Tell the Whole Story
Both algorithms have time complexity O(n).
Algorithm A sets up faster than B, but does more operations on the data
Algorithm A is the better choice for small values of n.
For values of n > 10, algorithm B is the better choice

42
A Misconception
A common misconception is that worst case running time is somehow
defined by big-Oh, and that best case is defined by big-Omega.

There is no formal relationship like this.

However, worst case and big-Oh are commonly used together,

because they are both techniques for finding an upper bound on
running time.

43
Relations over Asymptotic Notations
Maximum rule: O(f(n)+g(n)) = O( max(f(n),g(n)) )
Additive and Multiplicative Property:
If e(n) = O(g(n)) & f(n) = O(h(n)) then e(n) + f(n) = O(g(n) + h(n))
If e(n) = O(g(n)) & f(n) = O(h(n)) then e(n) • f(n) = O(g(n) • h(n))
Dichotomy Property: If f(n) = O(g(n)) & g(n) = O(f(n)) then f(n) = (g(n))
If f(n) = (g(n)) and g(n) = (f(n)) then f(n) = (g(n))
Reflexive Property: If f(n) = O(f(n)) and f(n) = (f(n)) and f(n) = (f(n))
f(n)  o(f(n)) and f(n)  (f(n))
Symmetry over : f(n) = (g(n))  g(n) = (f(n))
Transitivity Property:
f(n) = (g(n)) & g(n) = (h(n))  f(n) = (h(n))
f(n) = O(g(n)) & g(n) = O(h(n))  f(n) = O(h(n))
f(n) = (g(n)) & g(n) = (h(n))  f(n) = (h(n)) 44
f(n) = o (g(n)) & g(n) = o (h(n))  f(n) = o (h(n))
f(n) = (g(n)) & g(n) = (h(n))  f(n) = (h(n))