CS 240 – Data Structures and Data Management

Module 1: Introduction and Asymptotic Analysis

Mark Petrick
Based on lecture notes by many previous cs240 instructors

David R. Cheriton School of Computer Science, University of Waterloo

Fall 2020

References: Goodrich & Tamassia 1.1, 1.2, 1.3

Sedgewick 8.2, 8.3
version 2020-08-30 22:49

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 1 / 43

Outline

1 Introduction and Asymptotic Analysis

CS240 Overview
Algorithm Design
Analysis of Algorithms I
Asymptotic Notation
Analysis of Algorithms II
Example: Analysis of MergeSort
Helpful Formulas

Petrick (SCS, UW) CS240 – Module 1 Fall 2020

Outline

1 Introduction and Asymptotic Analysis

CS240 Overview
Algorithm Design
Analysis of Algorithms I
Asymptotic Notation
Analysis of Algorithms II
Example: Analysis of MergeSort
Helpful Formulas

Petrick (SCS, UW) CS240 – Module 1 Fall 2020

Course Objectives: What is this course about?

When first learning to program, we emphasize correctness: does your

program output the expected results?

Starting with this course, we will also be concerned with efficiency : is

your program using the computer’s resources (typically processor
time) efficiently?

We will study efficient methods of storing, accessing, and organizing

large collections of data.

Typical operations include: inserting new data items, deleting data

items, searching for specific data items, sorting.

Motivating examples: Digital Music Collection, English Dictionary

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 2 / 43

Course Objectives: What is this course about?

We will consider various abstract data types (ADTs) and how to

implement them efficiently using appropriate data structures.

There is a strong emphasis on mathematical analysis in the course.

Algorithms are presented using pseudo-code and analyzed using order
notation (big-Oh, etc.).

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 3 / 43

Course Topics

big-Oh analysis
priority queues and heaps
sorting, selection
binary search trees, AVL trees, B-trees
skip lists
hashing
quadtrees, kd-trees
range search
tries
string matching
data compression

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 4 / 43

CS Background

Topics covered in previous courses with relevant sections in [Sedgewick]:

arrays, linked lists (Sec. 3.2–3.4)

strings (Sec. 3.6)
stacks, queues (Sec. 4.2–4.6)
abstract data types (Sec. 4-intro, 4.1, 4.8–4.9)
recursive algorithms (5.1)
binary trees (5.4–5.7)
sorting (6.1–6.4)
binary search (12.4)
binary search trees (12.5)
probability and expectations (Goodrich & Tamassia, Section 1.3.4)

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 5 / 43

Outline

1 Introduction and Asymptotic Analysis

CS240 Overview
Algorithm Design
Analysis of Algorithms I
Asymptotic Notation
Analysis of Algorithms II
Example: Analysis of MergeSort
Helpful Formulas

Petrick (SCS, UW) CS240 – Module 1 Fall 2020

Problems (terminology)

First, we must introduce terminology so that we can precisely characterize

what we mean by efficiency.
Problem: Given a problem instance, carry out a particular computational
task.
Problem Instance: Input for the specified problem.
Problem Solution: Output (correct answer) for the specified problem
instance.
Size of a problem instance: Size(I) is a positive integer which is a
measure of the size of the instance I.
Example: Sorting problem

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 6 / 43

Algorithms and Programs

Algorithm: An algorithm is a step-by-step process (e.g., described in

pseudo-code) for carrying out a series of computations, given an arbitrary
problem instance I.
Solving a problem: An Algorithm A solves a problem Π if, for every
instance I of Π, A finds (computes) a valid solution for the instance I in
finite time.
Program: A program is an implementation of an algorithm using a
specified computer language.

In this course, our emphasis is on algorithms (as opposed to programs or

programming).

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 7 / 43

Algorithms and Programs

Pseudocode: a method of communicating an algorithm to another

person.
In contrast, a program is a method of communicating an algorithm to a
computer.

Pseudocode
omits obvious details, e.g. variable declarations,
has limited if any error detection,
sometimes uses English descriptions,
sometimes uses mathematical notation.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 8 / 43

Algorithms and Programs

For a problem Π, we can have several algorithms.

For an algorithm A solving Π, we can have several programs
(implementations).

Algorithms in practice: Given a problem Π

1 Design an algorithm A that solves Π. → Algorithm Design
2 Assess correctness and efficiency of A. → Algorithm Analysis
3 If acceptable (correct and efficient), implement A.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 9 / 43

Outline

1 Introduction and Asymptotic Analysis

CS240 Overview
Algorithm Design
Analysis of Algorithms I
Asymptotic Notation
Analysis of Algorithms II
Example: Analysis of MergeSort
Helpful Formulas

Petrick (SCS, UW) CS240 – Module 1 Fall 2020

Efficiency of Algorithms/Programs

How do we decide which algorithm or program is the most efficient

solution to a given problem?

In this course, we are primarily concerned with the amount of time a

program takes to run. → Running Time

We also may be interested in the amount of additional memory the

program requires. → Auxiliary space

The amount of time and/or memory required by a program will

depend on Size(I), the size of the given problem instance I.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 10 / 43

Running Time of Algorithms/Programs

First option: experimental studies

Write a program implementing the algorithm.

Run the program with inputs of varying size and composition.

Use a method like clock() (from time.h) to get an accurate

measure of the actual running time.

Plot/compare the results.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 11 / 43

Running Time of Algorithms/Programs
Shortcomings of experimental studies
Implementation may be complicated/costly.
Timings are affected by many factors: hardware (processor, memory),
software environment (OS, compiler, programming language), and
human factors (programmer).
We cannot test all inputs; what are good sample inputs?
We cannot easily compare two algorithms/programs.

We want a framework that:

Does not require implementing the algorithm.
Is independent of the hardware/software environment.
Takes into account all input instances.

We need some simplifications.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 12 / 43

Overview of Algorithm Analysis

We will develop several aspects of algorithm analysis in the next slides.

To overcome dependency on hardware/software:
Algorithms are presented in structured high-level pseudo-code which
is language-independent.
Analysis of algorithms is based on an idealized computer model.
Instead of time, count the number of primitive operations
The efficiency of an algorithm (with respect to time) is measured in
terms of its growth rate (this is called the complexity of the
algorithm).

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 13 / 43

Random Access Machine

Random Access Machine (RAM) model:

A set of memory cells, each of which stores one item (word) of data.
Implicit assumption: memory cells are big enough to hold the items
that we store.
Any access to a memory location takes constant time.
Any primitive operation takes constant time.
Implicit assumption: primitive operations have fairly similar, though
different, running time on different systems
The running time of a program is proportional to the number of
memory accesses plus the number of primitive operations.

This is an idealized model, so these assumptions may not be valid for a

“real” computer.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 14 / 43

Running Time Simplifications

We will simplify our analysis by considering the behaviour of algorithms for

large inputs sizes.

Example 1: What is larger, 100n or 10n2 ?

Example 2: What is larger, 1000000n + 200000000000000 or
0.01n2 ?

To simplify comparisons, use order notation

Informally: ignore constants and lower order terms

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 15 / 43

Outline

1 Introduction and Asymptotic Analysis

CS240 Overview
Algorithm Design
Analysis of Algorithms I
Asymptotic Notation
Analysis of Algorithms II
Example: Analysis of MergeSort
Helpful Formulas

Petrick (SCS, UW) CS240 – Module 1 Fall 2020

Order Notation
O-notation: f (n) ∈ O(g(n)) if there exist constants c > 0 and n0 > 0
such that |f (n)| ≤ c |g(n)| for all n ≥ n0 .
Example: f (n) = 75n + 500 and g(n) = 5n2 (e.g. c = 1, n0 = 20)

3,000

2,500

2,000

1,500

1,000

500

0
0 5 10 15 20 25

Note: The absolute value signs in the definition are irrelevant for analysis
of run-time or space, but are useful in other applications of asymptotic
notation.
Petrick (SCS, UW) CS240 – Module 1 Fall 2020 16 / 43
Example of Order Notation

In order to prove that 2n2 + 3n + 11 ∈ O(n2 ) from first principles, we need

to find c and n0 such that the following condition is satisfied:

0 ≤ 2n2 + 3n + 11 ≤ c n2 for all n ≥ n0 .

note that not all choices of c and n0 will work.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 17 / 43

Aymptotic Lower Bound

We have 2n2 + 3n + 11 ∈ O(n2 ).

But we also have 2n2 + 3n + 11 ∈ O(n10 ).
We want a tight asymptotic bound.

Ω-notation: f (n) ∈ Ω(g(n)) if there exist constants c > 0 and n0 > 0

such that c |g(n)| ≤ |f (n)| for all n ≥ n0 .

Θ-notation: f (n) ∈ Θ(g(n)) if there exist constants c1 , c2 > 0 and n0 > 0

such that c1 |g(n)| ≤ |f (n)| ≤ c2 |g(n)| for all n ≥ n0 .

f (n) ∈ Θ(g(n)) ⇔ f (n) ∈ O(g(n)) and f (n) ∈ Ω(g(n))

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 18 / 43

Example of Order Notation
Prove that f (n) = 2n2 + 3n + 11 ∈ Ω(n2 ) from first principles.

Prove that 12 n2 − 5n ∈ Ω(n2 ) from first principles.

Prove that logb (n) ∈ Θ(log n) for all b > 1 from first principles.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 19 / 43

Strictly smaller/larger asymptotic bounds

We have f (n) = 2n2 + 3n + 11 ∈ Θ(n2 ).

How to express that f (n) is asymptotically strictly smaller than n3 ?

o-notation: f (n) ∈ o(g(n)) if for all constants c > 0, there exists a

constant n0 > 0 such that |f (n)| ≤ c |g(n)| for all n ≥ n0 .
ω-notation: f (n) ∈ ω(g(n)) if g(n) ∈ o(f (n)).
Rarely proved from first principles.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 20 / 43

Algebra of Order Notations

Identity rule: f (n) ∈ Θ(f (n))

Transitivity:
If f (n) ∈ O(g(n)) and g(n) ∈ O(h(n)) then f (n) ∈ O(h(n)).
If f (n) ∈ Ω(g(n)) and g(n) ∈ Ω(h(n)) then f (n) ∈ Ω(h(n)).

Maximum rules: Suppose that f (n) > 0 and g(n) > 0 for all n ≥ n0 .
Then:
O(f (n) + g(n)) = O(max{f (n), g(n)})
Ω(f (n) + g(n)) = Ω(max{f (n), g(n)})

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 21 / 43

Techniques for Order Notation

Suppose that f (n) > 0 and g(n) > 0 for all n ≥ n0 . Suppose that

f (n)
L = lim (in particular, the limit exists).
n→∞ g(n)

Then 
o(g(n)) if L = 0


f (n) ∈ Θ(g(n)) if 0 < L < ∞

ω(g(n)) if L = ∞.


The required limit can often be computed using l’Hôpital’s rule. Note that
this result gives sufficient (but not necessary) conditions for the stated
conclusions to hold.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 22 / 43

Example 1
Let f (n) be a polynomial of degree d ≥ 0:

f (n) = cd nd + cd−1 nd−1 + · · · + c1 n + c0

for some cd > 0.

Then f (n) ∈ Θ(nd ):

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 23 / 43

Example 2
Prove that n(2 + sin nπ/2) is Θ(n). Note that limn→∞ (2 + sin nπ/2) does
not exist.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 24 / 43

Example 2
Prove that n(2 + sin nπ/2) is Θ(n). Note that limn→∞ (2 + sin nπ/2) does
not exist.

60

40

20

0
0 5 10 15 20 25

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 24 / 43

Relationships between Order Notations

f (n) ∈ Θ(g(n)) ⇔ g(n) ∈ Θ(f (n))

f (n) ∈ O(g(n)) ⇔ g(n) ∈ Ω(f (n))
f (n) ∈ o(g(n)) ⇔ g(n) ∈ ω(f (n))

f (n) ∈ o(g(n)) ⇒ f (n) ∈ O(g(n))

f (n) ∈ o(g(n)) ⇒ f (n) 6∈ Ω(g(n))
f (n) ∈ ω(g(n)) ⇒ f (n) ∈ Ω(g(n))
f (n) ∈ ω(g(n)) ⇒ f (n) 6∈ O(g(n))

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 25 / 43

Growth Rates

If f (n) ∈ Θ(g(n)), then the growth rates of f (n) and g(n) are the
same.
If f (n) ∈ o(g(n)), then we say that the growth rate of f (n) is
less than the growth rate of g(n).
If f (n) ∈ ω(g(n)), then we say that the growth rate of f (n) is
greater than the growth rate of g(n).
Typically, f (n) may be “complicated” and g(n) is chosen to be a very
simple function.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 26 / 43

Example 3

Compare the growth rates of log n and n.

Now compare the growth rates of (log n)c and nd (where c > 0 and d > 0
are arbitrary numbers).

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 27 / 43

Common Growth Rates

Commonly encountered growth rates in analysis of algorithms include the

following (in increasing order of growth rate):
Θ(1) (constant complexity ),
Θ(log n) (logarithmic complexity ),
Θ(n) (linear complexity ),
Θ(n log n)(linearithmic),
Θ(n logk n), for some constant k (quasi-linear ),
Θ(n2 ) (quadratic complexity ),
Θ(n3 ) (cubic complexity ),
Θ(2n ) (exponential complexity ).

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 28 / 43

How Growth Rates Affect Running Time

It is interesting to see how the running time is affected when the size of
the problem instance doubles (i.e., n → 2n).
constant complexity: T (n) = c
logarithmic complexity: T (n) = c log n
linear complexity: T (n) = cn
linearithmic Θ(n log n): T (n) = cn log n
quadratic complexity: T (n) = cn2
cubic complexity: T (n) = cn3
exponential complexity: T (n) = c2n

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 29 / 43

How Growth Rates Affect Running Time

It is interesting to see how the running time is affected when the size of
the problem instance doubles (i.e., n → 2n).
constant complexity: T (n) = c T (2n) = c.
logarithmic complexity: T (n) = c log n
linear complexity: T (n) = cn
linearithmic Θ(n log n): T (n) = cn log n
quadratic complexity: T (n) = cn2
cubic complexity: T (n) = cn3
exponential complexity: T (n) = c2n

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 29 / 43

How Growth Rates Affect Running Time

It is interesting to see how the running time is affected when the size of
the problem instance doubles (i.e., n → 2n).
constant complexity: T (n) = c T (2n) = c.
logarithmic complexity: T (n) = c log n T (2n) = T (n) + c.
linear complexity: T (n) = cn
linearithmic Θ(n log n): T (n) = cn log n
quadratic complexity: T (n) = cn2
cubic complexity: T (n) = cn3
exponential complexity: T (n) = c2n

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 29 / 43

How Growth Rates Affect Running Time

It is interesting to see how the running time is affected when the size of
the problem instance doubles (i.e., n → 2n).
constant complexity: T (n) = c T (2n) = c.
logarithmic complexity: T (n) = c log n T (2n) = T (n) + c.
linear complexity: T (n) = cn T (2n) = 2T (n).
linearithmic Θ(n log n): T (n) = cn log n
quadratic complexity: T (n) = cn2
cubic complexity: T (n) = cn3
exponential complexity: T (n) = c2n

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 29 / 43

How Growth Rates Affect Running Time

It is interesting to see how the running time is affected when the size of
the problem instance doubles (i.e., n → 2n).
constant complexity: T (n) = c T (2n) = c.
logarithmic complexity: T (n) = c log n T (2n) = T (n) + c.
linear complexity: T (n) = cn T (2n) = 2T (n).
linearithmic Θ(n log n): T (n) = cn log n T (2n) = 2T (n) + 2cn.
quadratic complexity: T (n) = cn2
cubic complexity: T (n) = cn3
exponential complexity: T (n) = c2n

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 29 / 43

How Growth Rates Affect Running Time

It is interesting to see how the running time is affected when the size of
the problem instance doubles (i.e., n → 2n).
constant complexity: T (n) = c T (2n) = c.
logarithmic complexity: T (n) = c log n T (2n) = T (n) + c.
linear complexity: T (n) = cn T (2n) = 2T (n).
linearithmic Θ(n log n): T (n) = cn log n T (2n) = 2T (n) + 2cn.
quadratic complexity: T (n) = cn2 T (2n) = 4T (n).
cubic complexity: T (n) = cn3
exponential complexity: T (n) = c2n

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 29 / 43

How Growth Rates Affect Running Time

It is interesting to see how the running time is affected when the size of
the problem instance doubles (i.e., n → 2n).
constant complexity: T (n) = c T (2n) = c.
logarithmic complexity: T (n) = c log n T (2n) = T (n) + c.
linear complexity: T (n) = cn T (2n) = 2T (n).
linearithmic Θ(n log n): T (n) = cn log n T (2n) = 2T (n) + 2cn.
quadratic complexity: T (n) = cn2 T (2n) = 4T (n).
cubic complexity: T (n) = cn3 T (2n) = 8T (n).
exponential complexity: T (n) = c2n

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 29 / 43

How Growth Rates Affect Running Time

It is interesting to see how the running time is affected when the size of
the problem instance doubles (i.e., n → 2n).
constant complexity: T (n) = c T (2n) = c.
logarithmic complexity: T (n) = c log n T (2n) = T (n) + c.
linear complexity: T (n) = cn T (2n) = 2T (n).
linearithmic Θ(n log n): T (n) = cn log n T (2n) = 2T (n) + 2cn.
quadratic complexity: T (n) = cn2 T (2n) = 4T (n).
cubic complexity: T (n) = cn3 T (2n) = 8T (n).
exponential complexity: T (n) = c2n T (2n) = (T (n))2 /c.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 29 / 43

Outline

1 Introduction and Asymptotic Analysis

CS240 Overview
Algorithm Design
Analysis of Algorithms I
Asymptotic Notation
Analysis of Algorithms II
Example: Analysis of MergeSort
Helpful Formulas

Petrick (SCS, UW) CS240 – Module 1 Fall 2020

Techniques for Algorithm Analysis
Goal: Use asymptotic notation to simplify run-time analysis.
Running time of an algorithm depends on the input size n.

Test1(n)
1. sum ← 0
2. for i ← 1 to n do
3. for j ← i to n do
4. sum ← sum + (i − j)2
5. return sum

Identify primitive operations that require Θ(1) time.

The complexity of a loop is expressed as the sum of the complexities
of each iteration of the loop.
Nested loops: start with the innermost loop and proceed outwards.
This gives nested summations.
Petrick (SCS, UW) CS240 – Module 1 Fall 2020 30 / 43
Techniques for Algorithm Analysis
Two general strategies are as follows.
Strategy I: Use Θ-bounds throughout the analysis and obtain a Θ-bound
for the complexity of the algorithm.
Strategy II: Prove a O-bound and a matching Ω-bound separately .
Use upper bounds (for O-bounds) and lower bounds (for Ω-bound) early
and frequently.
This may be easier because upper/lower bounds are easier to sum.

Test2(A, n)
1. max ← 0
2. for i ← 1 to n do
3. for j ← i to n do
4. sum ← 0
5. for k ← i to j do
6. sum ← A[k]
7. return max

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 31 / 43

Complexity of Algorithms
Algorithm can have different running times on two instances of the
same size.

Test3(A, n)
A: array of size n
1. for i ← 1 to n − 1 do
2. j ←i
3. while j > 0 and A[j] > A[j − 1] do
4. swap A[j] and A[j − 1]
5. j ←j −1

Let TA (I) denote the running time of an algorithm A on instance I.

Worst-case complexity of an algorithm: take the worst I
Average-case complexity of an algorithm: average over I

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 32 / 43

Complexity of Algorithms

Worst-case complexity of an algorithm: The worst-case running time

of an algorithm A is a function f : Z+ → R mapping n (the input size) to
the longest running time for any input instance of size n:

TA (n) = max{TA (I) : Size(I) = n}.

Average-case complexity of an algorithm: The average-case running

time of an algorithm A is a function f : Z+ → R mapping n (the input
size) to the average running time of A over all instances of size n:

1
TAavg (n) =
X
TA (I).
|{I : Size(I) = n}| {I:Size(I)=n}

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 33 / 43

O-notation and Complexity of Algorithms

It is important not to try and make comparisons between algorithms

using O-notation.

For example, suppose algorithm A1 and A2 both solve the same

problem, A1 has worst-case run-time O(n3 ) and A2 has worst-case
run-time O(n2 ).

Observe that we cannot conclude that A2 is more efficient than A1

for all input!
1 The worst-case run-time may only be achieved on some instances.
2 O-notation is an upper bound. A1 may well have worst-case run-time
O(n). If we want to be able to compare algorithms, we should always
use Θ-notation.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 34 / 43

Outline

1 Introduction and Asymptotic Analysis

CS240 Overview
Algorithm Design
Analysis of Algorithms I
Asymptotic Notation
Analysis of Algorithms II
Example: Analysis of MergeSort
Helpful Formulas

Petrick (SCS, UW) CS240 – Module 1 Fall 2020

Design of MergeSort

Input: Array A of n integers

Step 1: We split A into two subarrays: AL consists of the first d n2 e
elements in A and AR consists of the last b n2 c elements in A.

Step 2: Recursively run MergeSort on AL and AR .

Step 3: After AL and AR have been sorted, use a function Merge to

merge them into a single sorted array.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 35 / 43

MergeSort

MergeSort(A, ` ← 0, r ← n − 1, S ← NIL)
A: array of size n, 0 ≤ ` ≤ r ≤ n − 1
1. if S is NIL initialize it as array S[0..n − 1]
2. if (r ≤ `) then
3. return
4. else
5. m = (r + `)/2
6. MergeSort(A, `, m, S)
7. MergeSort(A, m + 1, r , S)
8. Merge(A, `, m, r , S)

Two tricks to reduce run-time and auxiliary space:

The recursion uses parameters that indicate the range of the array
that needs to be sorted.
The array used for copying is passed along as parameter.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 36 / 43

Merge

Merge(A, `, m, r , S)
A[0..n − 1] is an array, A[`..m] is sorted, A[m + 1..r ] is sorted
S[0..n − 1] is an array
1. copy A[`..r ] into S[`..r ]
2. int iL ← `; int iR ← m + 1;
3. for (k ← `; k ≤ r ; k++) do
4. if (iL > m) A[k] ← S[iR ++]
5. else if (iR > r ) A[k] ← S[iL ++]
6. else if (S[iL ] ≤ S[iR ]) A[k] ← S[iL ++]
7. else A[k] ← S[iR ++]

Merge takes time Θ(r − ` + 1), i.e., Θ(n) time for merging n elements.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 37 / 43

Analysis of MergeSort
Let T (n) denote the time to run MergeSort on an array of length n.
Step 1 takes time Θ(n)
Step 2 takes time T d n2 e + T b n2 c

Step 3 takes time Θ(n)

The recurrence relation for T (n) is as follows:
(
T d n2 e + T b n2 c + Θ(n)



if n > 1
T (n) =
Θ(1) if n = 1.

It suffices to consider the following exact recurrence, with constant factor

c replacing Θ’s:
(
T d n2 e + T b n2 c + cn



if n > 1
T (n) =
c if n = 1.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 38 / 43

Analysis of MergeSort

The following is the corresponding sloppy recurrence

(it has floors and ceilings removed):
(
n


2T 2 + cn if n > 1
T (n) =
c if n = 1.

The exact and sloppy recurrences are identical when n is a power of 2.

The recurrence can easily be solved by various methods when n = 2j .
The solution has growth rate T (n) ∈ Θ(n log n).
It is possible to show that T (n) ∈ Θ(n log n) for all n
by analyzing the exact recurrence.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 39 / 43

Some Recurrence Relations

Recursion resolves to example

T (n) = T (n/2) + Θ(1) T (n) ∈ Θ(log n) Binary search
T (n) = 2T (n/2) + Θ(n) T (n) ∈ Θ(n log n) Mergesort
T (n) = 2T (n/2) + Θ(log n) T (n) ∈ Θ(n) Heapify (→ later)
T (n) = T (cn) + Θ(n) T (n) ∈ Θ(n) Selection
for some 0 < c < 1 (→ later)
√
T (n) = 2T (n/4) + Θ(1) T (n) ∈ Θ( n) Range Search
(→ later)
√
T (n) = T ( n) + Θ(1) T (n) ∈ Θ(log log n) Interpolation Search
(→ later)

Once you know the result, it is (usually) easy to prove by induction.

Many more recursions, and some methods to find the result, in cs341.

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 40 / 43

Outline

1 Introduction and Asymptotic Analysis

CS240 Overview
Algorithm Design
Analysis of Algorithms I
Asymptotic Notation
Analysis of Algorithms II
Example: Analysis of MergeSort
Helpful Formulas

Petrick (SCS, UW) CS240 – Module 1 Fall 2020

Order Notation Summary

O-notation: f (n) ∈ O(g(n)) if there exist constants c > 0 and n0 > 0

such that |f (n)| ≤ c |g(n)| for all n ≥ n0 .
Ω-notation: f (n) ∈ Ω(g(n)) if there exist constants c > 0 and n0 > 0
such that c |g(n)| ≤ |f (n)| for all n ≥ n0 .
Θ-notation: f (n) ∈ Θ(g(n)) if there exist constants c1 , c2 > 0 and n0 > 0
such that c1 |g(n)| ≤ |f (n)| ≤ c2 |g(n)| for all n ≥ n0 .
o-notation: f (n) ∈ o(g(n)) if for all constants c > 0, there exists a
constant n0 > 0 such that |f (n)| ≤ c |g(n)| for all n ≥ n0 .
ω-notation: f (n) ∈ ω(g(n)) if for all constants c > 0, there exists a
constant n0 > 0 such that c |g(n)| ≤ |f (n)| for all n ≥ n0 .

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 41 / 43

Useful Sums
Arithmetic sequence:
Pn−1 Pn−1 dn(n−1)
i=0 i = ??? i=0 (a + di) = na + 2 ∈ Θ(n2 ) if d 6= 0.

Geometric sequence:
rn − 1

a ∈ Θ(r n−1 ) if r > 1


 r −1



∈ Θ(n)
Pn−1 i Pn−1
i=0 2 = ??? i=0 a ri = na if r = 1
1 − rn



 a ∈ Θ(1) if 0 < r < 1.


1−r
Harmonic sequence:
Pn 1
Hn := ni=1 1
= ln n + γ + o(1) ∈ Θ(log n)
P
i=1 i = ??? i

A few more:
Pn 1 Pn 1 π2
i=1 i 2 = ??? i=1 i 2 = 6 ∈ Θ(1)
Pn k Pn k
i=1 i = ??? i=1 i ∈ Θ(nk+1 ) for k ≥ 0

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 42 / 43

Useful Math Facts
Logarithms:
c = logb (a) means b c = a. E.g. n = 2log n .
log(a) (in this course) means log2 (a)
log(a · c) = log(a)+ log(c), log(ac ) = c log(a)
logc a 1
logb (a) = logc b = loga (b) , alogb c = c logb a
d 1
ln(x ) = natural log = loge (x ), dx ln x = x
concavity: α log x +(1−α) log y ≤ log(αx +(1−α)y ) for 0 ≤ α ≤ 1
Factorial:
n! := n(n − 1)(n − 2) · · · · 2 · 1 = # ways to permute n elements
log(n!) = log n + log(n − 1) + · · · + log 2 + log 1 ∈ Θ(n log n)
Probability and moments:
E [aX ] = aE [X ], E [X + Y ] = E [X ] + E [Y ] (linearity of expectation)

Petrick (SCS, UW) CS240 – Module 1 Fall 2020 43 / 43