Chapter 1.

Basics of
Algorithm Analysis

Slides by Kevin Wayne.

Copyright © 2005 Pearson-Addison Wesley.
All rights reserved.
1.3.1 Time Complexity of an Algorithm
Purpose

• To estimate how long a program will run

• To estimate the largest input that can reasonably be given to
the program
• To compare the efficiency of different algorithms
• To choose an algorithm for an application
Time complexity is a function

Time for a sorting algorithm is different for sorting 10 numbers

and sorting 1,000 numbers
Time complexity is a function: Specifies how the running time
depends on the size of the input.
Function mapping
“size” of input

“time” ( ) executed by algorithm

Definition of time?
Definition of time?

● # of seconds Problem: machine dependent

● # lines of code executed Problem: lines of diff. complexity
● # of simple operations performed

this is what we will use

Size of input instance?

Formally: Size is number of bits to represent instance

But we can work with anything reasonable

reasonable = within a constant factor of number of bits

Size of input instance

Ex 1:
83920

• # of bits → n = 17 bits
• # of digits → n = 5 digits Which are reasonable?
• Value: 83920 → n = 83920
Size of input instance

Ex 1:
83920

• # of bits: 17 bits - Formal

• # of digits: 5 digits - Reasonable
#bits and #digits are always within constant factor ( ),
# of bits = 3.32*# of digits
Size of input instance

Ex 1:
83920

• # of bits: 17 bits - Formal

• # of digits: 5 digits - Reasonable
• Value: 83920 - Not reasonable
# of bits =
Value = , much bigger
Size of input instance

Ex 2:

10

14,23,25,30,31,52,62,79,88,98

• # of elements → n = 10

Is this reasonable?
Size of input instance

Ex 2:

10

14,23,25,30,31,52,62,79,88,98

● # of elements → n = 10 Reasonable
if each element has c bits, total number of bits is:
#bits = c * #elements
Time complexity is a function

Specifies how the running time depends on the size of the input

Function mapping

# of bits to represent input

# of basic operations ( ) executed by the algorithm

Which input of size n?

Q: There are 2n inputs of size n.

Which do we consider for the time complexity T(n)?

Worst instance

Worst-case running time. Consider the instance where the algorithm uses
largest number of basic operations

• Generally captures efficiency in practice

• Pessimistic view, but hard to find better measure
Time complexity

We reach our final definition of time complexity:

T(n) = number of basic operations the algorithm takes over the worst
instance of bit-size n

complexity
T(n)

input size n
Example

Func Find10(A) #A is array of 32-bit numbers

For i=1 to length(A)
If A[i]==10
Return i

Q: What is the time complexity ( ) of this algorithm?

A: ( ) ≈ ( /32) + 1
• Worst instance: the only “10” is in the last position
• A of bit-size n has n/32 numbers
• ≈ 1 simple operations per step (if), +1 for Return
1.3.2 Asymptotic Order of Growth
Asymptotic Order of Growth

Motivation: Determining the exact time complexity T(n) of an algorithm is

very hard and often does not make much sense.

Algorithm 1:
x←100
For i=1...N
Time complexity:
j←j+1 ■ 2N +1 assignments
If x>50 then ■ N comparisons
x←x+3 ■ 2N additions
Total: 5N+1 basic operations
End If
End For
Asymptotic Order of Growth

Algorithm 2:
x←20 Time complexity
For i=1...N ■ N + 1 assignments
x←3x ■ N multiplications
Total: 2N+1 basic operations
End For

Can we say Algorithm 2 is going to run faster than Algorithm 1?

Not clear, depends on the time it takes for addition, assignment,

multiplication
Asymptotic Order of Growth

● No vale mucho la pena complicar la metodología estimando

las constantes.
● En lugar de calcular T(n) exactamente, queremos sólo cotas
superiores (e inferiores) para T(n) ignorando factores
constantes.
Asymptotic Order of Growth

Upper bounds O

Informal: T(n) is O(f(n)) if T(n) grows with at most the same order of
magnitude as f(n) grows

T(n) is O(f(n)) T(n) is O(f(n))

both grow at same
order of magnitude
Recap

Time complexity of an algorithm

T(n) = number of basic operations the algorithm takes over the worst
instance of bit-size n

complexity
T(n)

input size n
Asymptotic Order of Growth

Upper bounds - Cota Superior O

Formal: T(n) is O(g(n)) if there exist constants ≥ 0 such that for all
≥ 0 we have.
T(n) ≤ c · g(n).

Equivalent: T(n) is O(g(n)) if there exists k ≥ 0 such that

Asymptotic Order of Growth

Upper bounds - Cota Superior O

Definición Formal: Sea g: N→[0,∞). Se define el conjunto de
funciones de orden O(g(n)) como:

Diremos que una función t: N →[0,∞) es de orden O de g si t ∈ O(g).

Intuitivamente, t ∈ O(g) indica que t está acotada superiormente por algún múltiplo
de g. Normalmente estaremos interesados en la menor función g tal que t
pertenezca a O(g)
Upper bounds - Cota Superior O

Propiedades de O
Veamos las propiedades de la cota superior. La demostración de todas ellas
se obtiene aplicando la definición formal.

1. Para cualquier función T se tiene que T ∈ O(T).

2. T ∈ O(g) ⇒ O(T) ⊂ O(g).
3. O(T) = O(g) ⇔ T ∈ O(g) y g ∈ O(T).
4. Si T ∈ O(g) y g ∈ O(h) ⇒ T ∈ O(h).
5. Si T ∈ O(g) y T ∈ O(h) ⇒ T ∈ O(min(g,h)).
6. Regla de la suma: Si T1 ∈ O(g) y T2 ∈ O(h) ⇒ T1 + T2 ∈
O(max(g,h)).
7. Regla del producto: Si T1 ∈ O(g) y T2 ∈ O(h) ⇒ T1·T2 ∈ O(g·h).
Upper bounds - Cota Superior O

8. Si existe , dependiendo de los valores que tome k obtenemos:

A. Si k ≠0 y k<∞ entonces O(T) = O(g).

B. Si k = 0 entonces T ∈O(g), es decir, O(T) ⊂ O(g), pero sin embargo se
verifica que g ∉O(T).
Obsérvese la importancia que tiene el que exista tal límite, pues si no existiese
(o fuera infinito) no podría realizarse tal afirmación.
Asymptotic Order of Growth

Exercise 1: T(n) = 32n2 + 17n + 32.

Say if T(n) is:

■ O(n2) ?
■ O(n3) ?
■ O(n) ?
Asymptotic Order of Growth

Exercise 1: T(n) = 32n2 + 17n + 32.

Say if T(n) is:

■ O(n2) ? Yes
■ O(n3) ? Yes
■ O(n) ? No

Solution: To show that T(n) is O(n2) we can:

- Use the first definition with c = 1000
- Use limits:

, which is a constant
Asymptotic Order of Growth

Exercise 2:
■ T(n) = 2n+1, is it O(2n) ?
■ T(n) = 22n , is it O(2n) ?
Asymptotic Order of Growth

Exercise 2:
■ T(n) = 2n+1, is it O(2n) ? Yes
■ T(n) = 22n , is it O(2n) ? No

Solution (second item): is not constant

Solution 2 (second item): To have 22n < c.2n we need c>2n. So c is not.
Asymptotic Bounds for Some Common Functions

Logarithms. logan is O(logbn) for any constants a, b>0

can avoid specifying the base

Logarithms. For every x>0, log n is O(nx)

log grows slower than every polynomial

Exponentials. For every r>1 and every d>0, nd is O(rn)

every exponential grows faster than every polynomial
Asymptotic Bounds for Some Common Functions

O(an)
O(nk)
O(n3)
O(n2)
O(n lg n)
O(n)

O(lg n)

O(1)

Donde: k>=4, a>1

Asymptotic Bounds for Some Common Functions

Exercise: is T(n) = 21·n·log n

• O( 2) ?
• O( 1.1) ?
• O( ) ?
Asymptotic Bounds for Some Common Functions

Exercise: is T(n) = 21·n·log n

• O( 2) ? Yes
• O( 1.1) ? Yes
• O( ) ? No

Solution (first item): Comparing 21·n·log n vs n2 is the same as comparing

21·log n vs n, and we know log n grows slower than n.

Solution 2 (first item): , which is at most a constant since

log n grows slower than n
Lower Bounds - Cota Inferior Ω

Informal: T(n) is Ω(g(n)) if T(n) grows with at least the same order of
magnitude as g(n) grows.

Formal: T(n) is Ω(g(n)) if there exist constants c>0 such that for all n we
have T(n) ≥ c·g(n).

Equivalent: T(n) is Ω(g(n)) if there exist constant k>0

Lower Bounds - Cota Inferior Ω

Definición Formal: Sea g: N→[0,∞). Se define el conjunto de funciones de

orden Ω(Omega) de g como:

Diremos que una función t:N →[0,∞) es de orden Ω de g si t ∈ Ω(g).

Lower Bounds - Cota Inferior Ω

Propiedades de Ω: Veamos las propiedades de la cota inferior Ω. La

demostración de todas ellas se obtiene de forma simple aplicando la
definición formal.

1. Para cualquier función T se tiene que T ∈ Ω(T).

2. T ∈ Ω(g) ⇒ Ω(T) ⊂ Ω(g).
3. Ω(T) = Ω(g) ⇔ T ∈ Ω(g) y g ∈ Ω(T).
4. Si T ∈ Ω(g) y g ∈ Ω(h) ⇒ T ∈ Ω(h).
5. Si T ∈ Ω(g) y T ∈ Ω(h) ⇒ T ∈ Ω(max(g,h)).
6. Regla de la suma: Si T1 ∈ Ω(g) y T2 ∈ Ω(h) ⇒ T1+T2 ∈ Ω(g+h).
7. Regla del producto: Si T1 ∈ Ω(g) y T2 ∈ Ω(h) ⇒ T1·T2 ∈ Ω(g·h).
Lower Bounds - Cota Inferior Ω

8. Si existe , dependiendo de los valores que tome k

obtenemos:
a) Si k ≠ 0 y k < ∞ entonces Ω(T) = Ω(g).
b) Si k = 0 se verifica que T ∉ Ω(g), pero sin embargo se
verifica que g ∈ Ω(T), es decir, Ω(g) ⊂ Ω(T).
Lower Bounds - Cota Inferior Ω

Exercise: T(n) = 32n2 + 17n + 32. Is T(n):

■ Ω(n) ?
■ Ω(n2) ?
■ Ω(n3) ?
Lower Bounds - Cota Inferior Ω

Exercise: T(n) = 32n2 + 17n + 32 Is T(n):

● Ω(n) ? Yes
● Ω(n2) ? Yes
● Ω(n3) ? No
Tight Bounds - Cota Promedio Θ
Tight bounds. T(n) is Θ(g(n)) if T(n) is both O(g(n)) and Ω(g(n)).

Formal: T(n) is Θ(g(n)) if there exist constants c>0 and d>0 such that for all n
we have
c·g(n) ≤ T(n) ≤ d·g(n)
d·g(n)

c·g(n)
Tight Bounds - Cota Promedio Θ
Definición Formal. Sea T: N→[0,∞). Se define el conjunto de funciones de
orden Θ (Theta) de g como:
Θ(T) = O(T) ∩ Ω(T)
o, lo que es igual:

Diremos que una función t :N→[0,∞) es de orden Θ de g si t ∈ Θ(g).

Intuitivamente, t ∈ Θ(g) indica que t está acotada tanto superior como

inferiormente por múltiplos de g, es decir, que t y g crecen de la misma
forma.
Tight Bounds - Cota Promedio Θ
Propiedades Θ: Veamos las propiedades de la cota exacta. La demostración
de todas ellas se obtiene también de forma simple aplicando la definición
formal y las propiedades de O y Ω.

1. Para cualquier función T se tiene que T ∈ Θ(T).

2. T ∈ Θ(g) ⇒ Θ(T) = Θ(g).
3. Θ(T) = Θ(g) ⇔ T ∈ Θ(g) y g ∈ Θ(T).
4. Si T ∈ Θ(g) y g ∈ Θ(h) ⇒ T ∈ Θ(h).
5. Regla de la suma: Si T1 ∈ Θ(g) y T2 ∈ Θ(h) ⇒ T1+T2 ∈ Θ
(max(g,h)).
6. Regla del producto: Si T1 ∈ Θ(g) y T2 ∈ Θ(h) ⇒ T1·T2 ∈ Θ(g·h).
Tight Bounds - Cota Promedio Θ

7. Si existe , dependiendo de los valores que tome k

obtenemos:

a) Si k ≠ 0 y k < ∞ entonces Θ(T) = Θ(g).

b) Si k = 0 se verifica que Θ(T) ≠ Θ(g), es decir, los órdenes
exactos de T y g son distintos.
Lower and Tight Bounds

Exercise: T(n) = 32n2 + 17n + 32.

Is T(n):
■ Θ(n2) ?
■ Θ(n) ?
■ Θ(n3) ?
Lower and Tight Bounds

Exercise: T(n) = 32n2 + 17n + 32

Is T(n):
● Θ(n2) ? Yes
● Θ(n) ? No
● Θ(n3) ? No
Lower and Tight Bounds
Exercise: Show that log(n!) is Θ(n log n)
Lower and Tight Bounds

Answer:
■ First we show that log (n!) = O(n log n)

log (n!) = log n + log (n-1) + … log 1 < n. log n, since the log function is
increasing

■ Now we show that log (n!) = Ω(n log n)

log (n!) = log n + log (n-1) + … log 1 >n/2. log (n/2) = n/2 (log n – 1)
Upper and Lower bounds

inputs of size n for algorithm A (cartoon)

Can we say that the time complexity of A is?

● O( 2) ? Yes, because largest complexity of algorithm is at most 2

● Ω( 2) ? No, there are inputs where complexity has larger order

● Ω(n) ? Yes

● O(n) ? No, there is no input where the complexity of the algorithm has order 2

● Ω(n3/2) ? No
Implication of Asymptotic Analysis

Hypothesis
■ Basic operations (addition, comparison, shifts, etc) takes at least
10ms and at most 50ms seconds (This is time unity = u )
Algorithms
■ Algorithm A executes 20n operations for the worst instance (O(n))
■ Algorithm B executes n2 operations for the worst instance (Ω(n2))
Conclusion
■ For a instance of size n, A spends at most 1000n ms
■ For the worst instance of size n, B spends at least 10 n2 ms
■ For n>100, A is faster than B in the worst case, regargless of
which operations they execute.
Allows us to tell which algorithm is faster (for large instances)
Notation

Slight abuse of notation. T(n) = O(f(n))

■ Be careful: Asymmetric:
– f(n) = 5n3; g(n) = 3n2
– f(n) = O(n3) = g(n)
– but f(n) ≠ g(n)

■ Better notation: T(n) ∈ O(f(n)).

Exercícios
Exercícios Kleinberg & Tardos, cap 2 da lista de exercícios
1.3.3 A Survey of Common Running Times
Linear Time: O(n)
Linear time. Running time is at most a constant factor times the size of the
input.

Computing the maximum. Compute maximum of n numbers a1, …, an.

max ← a1
for i = 2 to n {
if (ai > max)
max ← ai
}

[Link] all instances the algorithm executes a linear number of

operations
Linear Time: O(n)
Linear time. Running time is at most a constant factor times the size of the
input.

Finding an item x in a list. Test if x is in the list a1, …, an

Exist ← false
for i = 1 to n {
if (ai== x)
Exist ← true
break
}

[Link] some instances the algorithm is sublinear (e.g. x in the first

position)
Linear Time: O(n)
Merge. Combine two sorted lists A = a1,a2,…,an with B = b1,b2,…,bn into sorted
whole.

i = 1, j = 1
while (both lists are nonempty) {
if (ai ≤ bj) append ai to output list and increment i
else(ai ≤ bj)append bj to output list and increment j
}
append remainder of nonempty list to output list

Claim. Merging two lists of size k takes O(n) time (n=total size=2k).
Pf. After each comparison, the length of output list increases by 1.
Claim. Merging two lists of size n takes O(n) time.
Pf. After each comparison, the length of output list increases by 1.
O(n log n) Time

O(n log n) time. Arises in divide-and-conquer algorithms.

Sorting. Mergesort and heapsort are sorting algorithms that perform

O(n log n) comparisons.

Largest empty interval. Given n time-stamps x1, …, xn on which copies of a

file arrive at a server, what is largest interval of time when no copies of the
file arrive?

O(n log n) solution. Sort the [Link] the sorted list in order,
identifying the maximum gap between successive time-stamps.
Quadratic Time: O(n2)

Quadratic time. Enumerate all pairs of elements.

Closest pair of points. Given a list of n points in the plane (x1, y1),
…,(xn, yn), find the distance of the closest pair.
O(n2) solution. Try all pairs of points.

min ← (x1 - x2)2 + (y1 - y2)2

for i = 1 to n { don't need to
for j = i+1 to n { take square roots
d ← (xi - xj)2 + (yi - yj)2
if (d < min) see chapter 5
min ← d
}
}

Remark. Ω(n2) seems inevitable, but this is just an illusion.

Cubic Time: O(n3)
Cubic time. Enumerate all triples of elements.

Set disjointness. Let S1, …, Sn be subsets of {1, 2, …, n}. Is there a

disjoint pair of sets?

Set Representation. Assume that each set is represented as an incidence

vector.
n=8 and S={2,3,6}, S is represented by
1 2 3 4 5 6 7 8

0 1 1 0 0 1 0 0

n=8 and S={1,4}, S is represented by

1 2 3 4 5 6 7 8

1 0 0 1 0 0 0 0
Algorithm:
For i=1...n-1
For j=i+1...n
For k=1...n
If (Si(k)=Sj(k)=1)
Return ‘There are not disjoint sets’
End If
End For
End For
End For
Return ‘There are disjoint sets’
Cubic Time: O(n3)
1. A complexidade de tempo do algoritmo é O(n3)?
2. A complexidade de tempo do algoritmo é Ω(n3) ?
Cubic Time: O(n3)
1. A complexidade de tempo do algoritmo é O(n3)? SIM
2. A complexidade de tempo do algoritmo é Ω(n3) ? SIM

“Bad” instance: all sets are equal to {n} => algorithm makes Ω(n3) basic
operations
Exponential Time
1. Independent set. Given a graph, find the largest independent set?
a. O(n2 2n) solution. Enumerate all subsets.
S* ← φ
foreach subset S of nodes {
check whether S in an independent set
if (S is largest independent set seen so far) update S*
←S
}
}

2. Decrypt a numeric (0...9) password of n elements

_ _ ... _ _
The complexity of Algorithm is O(10n)
10 10 ... 10 10
n: elements
Polynomial Time

Polynomial time. Running time is O(nd) for some constant d

independent of the input size n.

Ex: T(n) = 32 2 and T(n)= n log(n) are polynomial time

We consider an algorithm efficient if time complexity is polynomial

Justification: It really works in practice!

■ Although 6.02 × 1023 × N20 is technically poly-time, it would be
useless in practice.
■ In practice, the poly-time algorithms that people develop almost
always have low constants and low exponents.
■ Breaking through the exponential barrier of brute force typically
exposes some crucial structure of the problem.
Polynomial Time
Complexity of Algorithm vs Complexity of Problem

There are many different algorithms for solving the same problem

Showing that an algorithm is Ω(n3) does not mean that we cannot find
another algorithm that solves this problem faster, say in O( 2)
Exercício

Exercício 1. Considere um algoritmo que recebe um número real x e o vetor

(a0,a1,…,an-1) como entrada e devolve
a0 + a1x + … + an-1xn-1

a)Desenvolva um algoritmo para resolver este problema que execute em

tempo quadrático. Faça a análise do algoritmo

b)Desenvolva um algoritmo para resolver este problema que execute em

tempo linear. Faça a análise do algoritmo
Exercício - Solução

a)
sum = 0
Para i= 0 até n-1 faça
aux ← ai
Para j:=1 até i Análise: Número de operações
elementares é igual a:
aux ← x . aux
T(n) = 1+2+3+ … + n-1 = n(n-1)/2 = O(n2)
Fim Para
sum ← sum + aux
Fim Para
Devolva sum
Exercício - Solução

b)
sum = a0
pot = 1
Para i= 1 até n-1 faça Análise: A cada loop são realizadas O(1)
pot ← [Link] operações elementares. Logo, o tempo
sum ← sum + [Link] é linear
Fim Para
Devolva sum
Recap

T(n) is ( ( )): T(n) grows “slower” than f(n)

T(n) is Ω( ( )): T(n) grows at least as fast as f(n)

T(n) is Θ( ( )): T(n) is both ( ( )) and Ω( ( ))

Exercised design and analysis of simple algorithms, giving upper

bound O(f(n))

right order of growth

Observations on Ω( ( ))

Func Find10(A) #A is array of 32-bit numbers

For i=1 to len(A)
If A[i]==10
Return i

Q: What is the time complexity ( ) of this algorithm? Give upper bound

O(.) and lower bound Ω(.)

A: Θ( ): In worst-case, does n iterations of the for => O(n) and Ω(n).

Point: We always consider worst instance, Omega(n) does not mean that all
instances take time ≥ ~ n
Observations on Ω( ( ))

Find closest pair of points, given input pairs (x1, y2),…,(xn, yn)

min ← (x1 - x2)2 + (y1 - y2)2

for i = 1 to n-1 {
for j = i+1 to n {
d ← (xi - xj)2 + (yi - yj)2
if (d < min)
min ← d
}
}

Q: Is this algo Ω( 2)?

A: Yes. Does exactly “combinação de n itens 2 a 2” iterations of for =>
n*(n-1)/2 iterations = 2/2 – /2 => quadratic growth
Observations on Ω( ( ))

Method 2: Write #iterations as big summation, lower bound

n + (n-1) + (n-2) + ... + 2 + 1 >= ??
min ← (x1 - x2)2 + (y1 - y2)2
Trick: Just keep the highest n/2 terms
for i = 1 to n-1 {
for j = i+1 to n { Back to example n + (n-1) + (n-2) + ... + 2 + 1
d ← (xi - xj)2 + (yi - yj)2
>= n + (n-1) + (n-2) + ... + n/2
if (d < min)
min ← d >= (n/2)*(n/2) = 2/4
}
}
Keep largest n/2
terms
Lower bounded each
term by minimum
Ex: Show that 12+22+...+n2 =Ω(n3)
1.3.4 A First Analysis of a Recursive Algorithm
Binary Search

Problem: Given a sorted list of numbers (increasing order)

a1,…an, decide if number x is in the list
Ex: x=14
Function bin_search(i,j, x) 1 2 3 5 7 10 14 17
if i = j
if a_i = x return TRUE
else return FALSE
end if 7 10 14 17
mid = floor((i+j)/2)
if x = a_mid
return x
else if x < a_mid
14 17
return bin_search(i, mid-1, x)
else if x > a_mid
return bin_search(mid+1, j, x)
end if

Function bin_search_main(x)
bin_search(1,n, x)
Binary Search Analysis

Binary search recurrence:

we will always ignore floor/ceiling

(the “sorting” slides has one slide that keeps the ceiling,
so you can see that it works)
Binary Search Analysis

Binary search recurrence:

Claim: The time complexity T(n) of binary search is at most c*log n

Proof 1: T(n) ≤ c + T(n/2) ≤ c + c + T(n/4) ≤.... ≤ c + c + ... + c

T(n) c log n terms

T(n/2) c

T(n/4) log2n c

... ...

T(2)
c
c log2n
Binary Search Analysis

Binary search recurrence:

Claim: The time complexity T(n) of binary search is at most c*log n

Proof 2: (induction) Base case: n=1

Now suppose that for n’ ≤ n – 1, ( ’) ≤ ∗ log( ’)

Then T(n) ≤ c + T(n/2) ≤ c + c*log(n/2) = c + c*(log n – 1) = c*log n

Recursive Algorithms

Exercício 2. Projete um algoritmo (recursivo) que recebe como entrada um

número real x e um inteiro positivo n e devolva xn. O algoritmo deve
executar O(log n) somas e multiplicações
Recursive Algorithms

Proc Pot(x,n)
Se n=0 return 1
Se n=1 return x
Se n é par Análise:
tmp←Pot(x,n/2) T(n)= c+ T(n/2) => T(n) é O(log n)
Return tmp*tmp
Senão n é ímpar
tmp←Pot(x,(n-1)/2)
Return x*tmp*tmp
Fim Se
Fim