Algorithms & Data Structures

• Professor Reza Sedaghat

• COE428: Engineering Algorithms & Data Structures

•Email address: rsedagha@ee.ryerson.ca
• Course outline: www.ee.ryerson.ca/~courses/COE428/
• Course References:
1) Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest. Introduction to Algorithms, MIT, 2002, ISBN: 0‐07‐
013151‐1 (McGraw‐Hill) (Course Text)

14
2 Running time

• The running time depends on the input: an

already sorted sequence is easier to sort.
• Parameterize the running time by the size of
the input, since short sequences are easier to
sort than long ones.
• Generally, we seek upper bounds on the
running time, because everybody likes a
guarantee.

15
Timing analyses

Worst-case: (usually)
• T(n) = maximum time of algorithm
on any input of size n.
Average-case: (sometimes)
• T(n) = expected time of algorithm
over all inputs of size n.
• Need assumption of statistical
distribution of inputs.
Best-case: (bogus)
• Cheat with a slow algorithm that
works fast on some input.
16
• Analyzing algorithms
• Analyzing an algorithm has come to mean predicting the resources that the
algorithm requires.

• Occasionally, resources such as memory, communication bandwidth, or

logic gates are of primary concern

• Most often it is computational time that we want to measure.

• Analysis of insertion sort

• The time taken by the INSERTION-SORT procedure depends on the
input: sorting a thousand numbers takes longer than sorting three numbers.

• Moreover, INSERTION-SORT can take different amounts of time to sort

two input sequences of the same size depending on how nearly sorted they
already are.

• In general, the time taken by an algorithm grows with the size of the input

• In general, the running time of a program is described as a function of the

size of its input.
17
• We need to define the terms "running time" and "input size“
• Input size
• For many problems the most natural measure is the number of
items for the input
•We shall indicate which input size measure is being used with
each problem we study.
• Running time
• The running time of an algorithm on a particular input is the
number of primitive operations or "steps" executed.
• It is convenient to define the notion of step so that it is as
machine-independent as possible
• One line may take a different amount of time than another line,
but we shall aassume that each execution of the i-th line takes
time ci, where ci is a constant.
18
2.2 Running time
• The INSERTION-SORT procedure with the time "cost" of each statement
and the number of times each statement is executed.

• Example: For each j = 2, 3, . . . , n where n = length[A], we let tj be the

number of times the “while” loop in line 5 is executed for that value of j

• Note that when a for or while loop exits in the usual way, due to the test
in the loop header, the test is executed one time more than the loop body.

19
• Running time
•The running time of the algorithm is the sum of running times for
each statement executed;

• A statement that takes ci steps to execute (cost) and is executed n

times will contribute ci . n to the total running time.

• To compute T(n), the running time of INSERTION-SORT, we

sum the products of the cost and times columns, obtaining

20
• Running time

21
• Running time

• Best case: The array is already sorted.

This running time can be expressed as an + b for constants a and b that depend on the
statement costs ci; it is thus a linear function of n.

T (n) = an + b

22
• Arithmetic series
• The summation

• Example: n = 4 4

 k  1  2  3  4  10
k 1
• Which came up when we analyzed insertion sort is an arithmetic series and has the
value

• Example: n = 4 4
1
k 
k 1 2
4(4  1)  10

23
• Running time

•Worst Case
• If the array is in reverse sorted order--that is, in decreasing
order--the worst case results.

• We must compare each element A[j] with each element in the

entire sorted subarray A[1. . j - 1], and so tj = j for j = 2,3, . . . , n.

24
• we find that in the worst case, the running time of INSERTION-SORT is

• This worst-case running time can be expressed as an2 + bn+ c for constants a, b, and c
that again depend on the statement costs ci; it is thus a quadratic function of n

25
•Running time
• We usually concentrate on finding the worst-case running
time: the longest running time for any input of size n.

•Reasons:
• The worst-case running time gives a guaranteed upper
bound on the running time for any input.
• For some algorithms, the worst case occurs often.
• For example, when searching, the worst case often occurs
when the item being searched for is not present, and
searches for absent items may be frequent.

26
• Order of growth
• Another abstraction to ease analysis and focus on the important features.
• Look only at the leading term of the formula for running time.
• Drop lower-order terms.
• Ignore the constant coefficient in the leading term.
• Example: For insertion sort, we already abstracted away the actual
statement costs to conclude that the worst-case running time is an2 + bn + c.
• Drop lower-order terms => an2 .
• Ignore constant coefficient => n2 .
• But we cannot say that the worst-case running time T (n) equals n2 .
• It grows like n2 . But it doesn’t equal n2 .
• We say that the running time is (n2)to capture the notion that the order
of growth is n2 .
•We usually consider one algorithm to be more efficient than another if its
worst case running time has a smaller order of growth.

27
 Machine‐independent time

What is insertion sort’s worst-case time?

• It depends on the speed of our computer:
• relative speed (on the same machine),
• absolute speed (on different machines).
BIG IDEA:
• Ignore machine-dependent constants.
• Look at growth of T(n) as n → ∞ .

28
 Asymptotic performance

When n gets large enough, a (n2) algorithm

always beats a (n3) algorithm.
• We shouldn’t ignore
asymptotically slower
algorithms, however.
• Real-world design
situations often call for a
T(n) careful balancing of
engineering objectives.
• Asymptotic analysis is a
useful tool to help to
n n0 structure our thinking.
29
30
31
32
33
34
35
36
37
38
39
2.3 Designing algorithms

• There are many ways to design algorithms.

• For example, insertion sort is incremental: having sorted A[1 ..j -1], place
A[ j ] correctly, so that A[1 ..j ] is sorted.

• Another common approach is “Divide and conquer” or “Recursion”

Recur means; return, happen again, be repeated
• Recursive algorithms often follow a general pattern:
• Divide the problem into a number of subproblems.
• Conquer the subproblems by solving them recursively.
• Base case: If the subproblems are small enough, just solve them by
brute force.
• Combine the subproblem solutions to give a solution to the original
problem.
40
• Recursion (example)
• Merge sort
• A sorting algorithm based on divide and conquer. Its worst-case running time
has a lower order of growth than insertion sort.
•Because we are dealing with subproblems, we state each subproblem as sorting
a subarray A[ p ..r]. Initially, p =1 and r = n, but these values change as we
recurse through subproblems.
• To sort A[ p ..r]:
• Divide by splitting into two subarrays A[ p ..q] and A[q +1 ..r], where q is
the halfway point of A[ p ..r].
• Conquer by recursively sorting the two subarrays A[ p ..q] and A[q +1 ..r].
• Combine by merging the two sorted subarrays A[ p ..q] and A[q +1 ..r] to
produce a single sorted subarray A[ p ..r]. To accomplish this step, we’ll
define a procedure MERGE (A, p, q, r)
• The recursion bottoms out when the subarray has just 1 element, so that it’s
trivially sorted. 41
Merge sort

p q q +1 r
5 2 4 6 1 3 2 6

5 2 4 6 1 3 2 6

5 2 4 6 1 3 2 6

Initial array 5 2 4 6 1 3 2 6

42
Merge sort

43