03: Algorithm Analysis

Book

Read sections 2.4.3 to 2.4.6 in Weiss, Data Structures and Algorithm Analysis in
Java.

2
Algorithm 1 for the Maximum Subsequence Sum Problem

3
Algorithm 1 for the Maximum Subsequence Sum Problem
● Consider what this algorithm does.
● Run the loops for a few times to understand what it does.
● It exhaustively tries all possibilities.
● For all combinations of all the values for the starting and ending points (i and
j), the partial sum (thisSum) is calculated and compared with the maximum
value so far.
● The running time is O(N3) and is entirely due to lines 7 and 8, the k loop.
● The precise analysis is obtained from the sum

which tells how many times line 8 is executed (the innermost loop which is an
O(1) operation).
4
Algorithm 1 for the Maximum Subsequence Sum Problem

● The sum can be evaluated inside out, using the formulas we have discussed
before, such as the formula for the sum of first N integers and first N squares.
● The innermost summation is

● Using the result, we can write the sum of j loop, which is the sum of first N −
i integers, as follows:

5
Algorithm 1 for the Maximum Subsequence Sum Problem
Now the i loop:

The N3 defines the running time. Remember that we ignore the constants. So, the
running time is O(N3).
6
Algorithm 2 for the Maximum Subsequence Sum Problem
● We can improve Algorithm 1 to avoid the cubic running time by removing a
for loop.
● Obviously, it is not always possible to remove a for loop.
● However, in this case, there are several unnecessary computations in
Algorithm 1.
● The inefficiency is in the following summation. Notice that:

● which means the k loop can be removed and adding only the element at
index j would be enough.
● Here is the code.

7
Algorithm 2 for the Maximum Subsequence Sum Problem

This algorithm is O(N2) and the analysis is even simpler. Let’s take a look at Algorithm
3.

8
Algorithm 3 for the Maximum Subsequence Sum Problem
● There is a recursive and relatively complicated O(NlogN) solution to this problem.
● The algorithm uses a “divide and conquer” strategy.
● Divide part: The idea is to split the problem into two roughly equal subproblems
which are then solved recursively.
● Conquer part: consists of patching together the two solutions of the subproblems,
and possibly doing a small amount of additional work, to arrive at a solution for the
whole problem.
● For this problem, the solution can either be in the left half, or the right half, or it
crosses the middle and is in both halves.
● If it crosses the middle, the answer should be the largest sum in the first half that
includes the last element, and the largest sum in the second half that includes the
first element... Let me illustrate.

9
Algorithm 3 for the Maximum Subsequence Sum Problem

● The largest sum in the first half is 6, A1 to A3, for the second it is 8, A6 to A7.
● The largest sum in the first half that includes the last element is 4, A1 to A4.
● The largest sum in the second that includes the first element is 7, A5 to A7.
● Thus, the largest sum that spans two halves is 4 + 7 = 11, A1 to A7. This
value is greater than both halves, and is the correct answer.

10
Algorithm 3 for the Maximum Subsequence Sum Problem

maxSumRec

maxSumRec

11
Algorithm 3 for the Maximum Subsequence Sum Problem

12
Algorithm 3 for the Maximum Subsequence Sum Problem
● Let’s analyze this. Let T(N) be the time it takes to solve a maximum subsequence
sum problem of size N.
● If N = 1, then the program takes constant amount of time to execute the lines for
the base case (lines 5 to 8): T(1) = O(1)
● Line 10 takes O(1)
● The recursive calls on lines 11 and 12 take T(N/2) units of time each, for a total
of 2T(N/2).
● The other bookkeeping lines, 15 and 22, take O(1) time.
● There are two for loops that operate on all elements, which takes O(N) time.
● We can ignore lines that have constant O(1) time when we have O(N), so the total
time is
T(1) = O(1)
T(N) = 2T(N/2) + O(N)

13
Algorithm 3 for the Maximum Subsequence Sum Problem
● To simplify the calculations, we replace O(N) with N. Since T(N) will be
expressed in terms of Big-Oh notation, this will not affect the answer.
● If T(N) = 2T(N/2) + N, and T(1) = 1, then T(2) = 2T(1) + 2 = 2 + 2 = 4,
and T(4) = 8 + 4 = 12, and T(8) = 24 + 8 = 32 and so on...
● These values can also be expressed as T(2) = 2 × 2 = 21 × 2,
T(4) = 4 × 3 = 22 × 3 and T(8) = 8 × 4 = 23 × 4.
● So, if N = 2k, then k = logN, and
T(N) = N × (k + 1) = Nk + N = N logN + N = O(N logN).
● Notice, however, that this analysis assumes that N is a power of 2.
● When N is not a power of 2, a more complicated analysis is required, but the Big-
Oh result remains unchanged.

14
Algorithm 3 for the Maximum Subsequence Sum Problem

Alternatively;
T(N) = 2T(N/2) + N and T(1) = 1
T(N) = 2(2T(N/4)+N/2) + N
= 4T(N/4) + 2N
= 4(2T(N/8)+N/4) + 2N
= 8T(N/8) + 3N = ... = 2kT(N/2k) + kN
If N = 2k then T(N) = N + kN = N log N + N = O(N log N)

15
Algorithm 4 for the Maximum Subsequence Sum Problem
to continue next week (Week 03)

16
Algorithm 4 for the Maximum Subsequence Sum Problem

● How can this work?

● Observation 1: If a[j] < 0 then it can not start an optimal sequence. Hence,
no negative subsequence can be a prefix in the optimal.
● Observation 2: If j is the first index causing sum < 0,

then we can advance to j + 1.

● Proof: Let p ∈ [i + 1 . . j]. Any subsequence starting at p is not larger than
the sequence starting at i, since j is the first index causing sum < 0.

17
Algorithm 4 for the Maximum Subsequence Sum Problem

● This algorithm is typical of many clever algorithms: the running time is

obvious, but the correctness is not.
● For these algorithms, formal correctness proofs (more formal than what we
just did), are almost always required.
● Even then many people still are not convinced.
● Additionally, many of such algorithms require trickier programming, leading to
longer development.
● But when these algorithms work, they run quickly, and we can test much of
the code logic by comparing it with an inefficient but easily implemented
brute-force algorithm using small input sizes.

18
Algorithm 4 for the Maximum Subsequence Sum Problem

● This fourth algorithm has one other advantage to the other three: at any point
in time, the algorithm can correctly give an answer to the problem for the data
it has already read.
● Algorithms that can do this are called online algorithms.
● An online algorithm requiring only constant space and running in linear time
is just about as good as it can get!

19
Logarithms in the Running Time

● The most confusing aspect of analyzing algorithms centers around the

logarithm.
● The general rule is: An algorithm is O(logN) if it takes constant (O(1)) time to
cut the problem size by a fraction, which is usually 1/2.
● On the other hand, if constant time is required to merely reduce the problem
by a constant amount, such as to make the problem smaller by 1, then the
algorithm is O(N).
● We usually presume that the input is preread, otherwise the algorithm is Ω(N).
● Let’s take a look at examples of logarithmic behaviour.

20
Binary Search
Binary Search: Given an integer X and integers A0,A1, . . . ,AN−1, which are presorted
and already in memory, find i such that Ai = X, or return i = −1 if X is not in the
input.

● We take advantage of the sorted list.

● We check if X is the middle element. If it is, then we are done.
● If X is smaller than the middle element, then we can apply the same approach to
the sorted subarray to the left of the middle element; and we do the same to the
right of the middle element if X is greater.
● With a swift stroke, we cut the problem in half!
● You should be able to write this code without any help. Here’s the code anyways.

21
Binary Search

22
Binary Search

● All the work done inside the loop takes O(1) per iteration, so the analysis
requires determining the number of times around the loop.
● The loop starts with high − low = N − 1 and finishes with high − low = −1.
● Every time through the loop the value high − low must be at least halved from
its previous value.
● Thus, the number of times around the loop is at most log(𝑁 − 1) + 2, which
is O(logN).

23
Binary Search

● Let high − low = N − 1 = d.

● Assume that 2k ≤ d < 2k+1. That is to say, let the difference between the
high and low values of the list to be between the two powers of 2.
● This implies,
k ≤ log d < k + 1 ⇒ k ≤ ⌈log d⌉ ≤ k + 1

and notice that the inequality changes when we take the ceiling of the
logarithm.

24
Binary Search

● After each iteration, new value for d may either be high − mid − 1 or
mid − 1 − low. Both of them are bounded from above as shown below.
Remember ⌊x⌋ ≤ x < ⌊x⌋ + 1 and mid = (high+low)/2 .

25
Binary Search

● Hence, after k iterations, d becomes 1.

● Loop iterates 2 more times where d takes the value 0 and -1 in this order. Thus, it
is repeated k + 2 times.

26
Euclid’s Algorithm
● This algorithm computes the greatest common divisor (Tr .OBEB or EBOB ).
● The greatest common divisor (gcd) of two integers is the largest integer that
divides both. Thus, gcd(50, 15) = 5.

27
Euclid’s Algorithm

● The algorithm computes gcd(m, n) assuming m ≥ n. If n > m the first iteration

of the loop swaps them.
● Fact: If m > n, then m mod n < m/2
● Proof: There are two cases.
○ If n ≤ m/2 then since the remainder is always smaller than n, the theorem is true for this case.
○ If n > m/2: but then n goes into m once with a remainder m − n < m/2, proving the theorem.
● This also shows that after two iterations the remainder is at most half of its
original value, and therefore the algorithm takes O(logN) time to run.

28
Exponentiation

● Algorithm pow(X, N) raises an integer to an integer power.

● We will count the number of multiplications as the measurement of running
time.
● The obvious algorithm to compute XN uses N − 1 multiplications.
● A recursive algorithm can do better.

29
Exponentiation

● Lines 3 and 4 handle the base cases of the recursion.

● XN = (X2)N/2, if N is even.
● XN = (X2)(N-1)/2 × X, if N is odd.
● The number of multiplications required is clearly 2 logN because at most two
multiplications are required to halve the problem.

30
Exponentiation
● It is interesting to note how much the code can be tweaked.
● The base case for N == 1 is not necessary, since line 6 does the right thing.
● Line 6 can be written as follows without affecting the correctness of the program.
The sequence of multiplications is the same as before.

31
Exponentiation

● However, all of the alternatives for line 5 are bad, even if they look correct.
● Lines 2 and 3 are incorrect because pow(X, 2) cannot make any progress
and an infinite loop results.
● Using line 4 affects the efficiency, because there are now two recursive calls
of size N/2 instead of only one.

32
Checking Your Analysis

● Once an analysis has been performed, it is desirable to see if the answer is

correct and as good as possible.
● One way to do this is to code up the program and see if the empirically
observed running time matches the running time predicted by the analysis.
● When n doubles, the running time goes up by a factor of 2 for linear
programs, 4 for quadratic programs, and 8 for cubic programs.
● Programs that run in logarithmic time take only an additive constant longer
when n doubles, and programs that run in O(n log n) take slightly more than
twice as long to run under the same circumstances.

33
Checking Your Analysis

● Another commonly used trick to verify that some program is O(f(n)) is to

compute the values T(n)/f(n) for a range of n where T(n) is the empirically
observed running time.
● If f(n) is a tight answer for the running time, then the computed values
converge to a positive constant.
● If f(n) is an over-estimate, the values converge to zero.
● If f(n) is an under- estimate and hence wrong, the values diverge.

34
Checking Your Analysis

● This program segment computes the probability that two distinct positive
integers, less than or equal to N and chosen randomly, are relatively prime
(as N gets large, the answer approaches 6/π2).
● What is the running time complexity?

35
Checking Your Analysis
● What is the running time complexity?
● O(N2 logN)
● Are you sure?

36
Checking Your Analysis
As the table dictates, last column is most likely to be the correct one.

37
Homework Assignments

● 2.13, 2.14, 2.15, 2.22, 2.25, 2.26, 2.28

● You are requested to study and solve the exercises.
● Note that these are for you to practice only. You are not to deliver the results.

38
References

● CE221 Lecture Slides by Prof. Dr. Cem Evrendilek

● Data Structures and Algorithm Analysis in Java, Third Edition, Mark Allen
Weiss
● Algorithm Design, Jon Kleinberg and Eva Tardos
● Data Structures and Algorithms in C++, Michael Goodrich and Roberto
Tamassia and David Mount
● Introduction to Algorithms, Third Edition, Thomas H. Cormen and Charles E.
Leiserson and Ronald L. Rivest and Clifford Stein
● Edited by Assoc. Prof. Dr. Kaya Oğuz

39