02: Algorithm Analysis

Book

● Read sections 2.1 to 2.4.2 in Weiss, Data Structures and Algorithm Analysis
in Java

2
Algorithms

Today we will discuss

● How to estimate the time required for a program,

● How to reduce the running time of a program from days or years to fractions
of a second.

3
Algorithms

● Definition: An algorithm is a clearly specified set of simple instructions to be

followed to solve a problem.

● Once an algorithms is given and somehow decided to be correct, an

important step is to determine how much the algorithm will require in the way
of resources, such as time and space.

4
Mathematical Background

● Given two functions, f(N) and g(N), there are usually points where one
function is smaller than the other function, so stating that f(N) < g(N) does
not make sense.
● Instead, we compare their relative rates of growth.
● Let f(N) = 1000N and g(N) = N2.
● For smaller values, f(N) > g(N), however N2 grows at a faster rate, and
eventually g(N) will be the larger function.
● The turning point is N = 1000.

5
Mathematical Background
● The definition below says that once past some point n0, c · f(N) is always at
least as large as T(N), so that if constants are ignored, f(N) is at least as big
as T(N).
● It can also be said that the growth rate of T(N) is less than or equal to that of
f(N).
● Definition: T(N) = O(f(N)) if there are positive constants c and n0 such that
T(N) ≤ c f(N) when N ≥ n0.
● This notation is known as Big-Oh notation.
● T(N) denotes the time taken by our algorithm (or our program), N denotes
the input size, and f(N) denotes the functions used to categorize these
algorithms; such as N, or N2, or log(N).

6
Mathematical Background

7
Mathematical Background

● Suppose T(N) = pN2 + qN + r for positive constants p, q, and r, and we

would like to claim that T(N) is O(N2).
● For all N ≥ 1, we have qN ≤ qN2 and r ≤ rN2. So,
T(N) = pN2 + qN + r ≤ pN2 + qN2 + rN2 = (p + q + r)N2
for all N ≥ 1.
● This inequality is exactly what the definition of Big-Oh requires:
T(N) ≤ cN2
where c = p + q + r and n0 ≥ 1.

8
Mathematical Background

● Definition: T(N) = Ω(g(N)) if there are positive constants c and n0 such that
T(N) ≥ cg(N) when N ≥ n0.

● This definition says that the growth rate of T(N) is greater than or equal to
that of g(N).

9
Mathematical Background

● Definition: T(N) = Θ(h(N)) if and only if T(N) = O(h(N)) and T(N) =

Ω(h(N)).

● This definition says that the growth rate of T(N) equals the growth rate of
h(N).

10
Mathematical Background

● Definition - Little Oh: T(N) = o(p(N)) if for all positive constants c there
exists an n0 such that T(N) < cp(N) when N > n0.
Less formally, T(N) = o(p(N)) if T(N) = O(p(N)) and T(N) ≠ Θ(p(N)).
● This definition says that the growth rate of T(N) is less than the growth rate of
p(N).
● This is different from Big-Oh because Big-Oh allows the possibility that the
growth rates are the same.

11
Mathematical Background

● T(N) = O(f(N)) means that the growth rate of T(N) is less than or equal to
that of f(N).
● For example, T(N) = O(N2) means T(N) does not grow faster than N2.
● To prove that some function T(N) = O(f(N)), we do not apply these
definitions formally, but use a repertoire of known results.
● In general, a proof is a very simple calculation and should not involve
calculus.

12
Mathematical Background

● When we say that T(N) = O(f(N)), we are guaranteeing that the function
T(N) grows at a rate no faster than f(N).
● This means f(N) is an upper bound on T(N).
● This also means that when f(N) = Ω(T(N)) (notice that we have swapped
functions), and T(N) is a lower bound on f(N)
● As an example, N3 grows faster than N2, so N2 = O(N3) or N3 = Ω(N2).

13
Mathematical Background

14
Mathematical Background

● Rule 1: If T1(N) = O(f(N)) and T2(N) = O(g(N)), then

○ T1(N) + T2(N) = O(f(N) + g(N)).
Intuitively and less formally, it is O(max(f(N), g(N))).
○ T1(N) × T2(N) = O(f(N) × g(N)).

● Assume that some part of your algorithm is O(N) and the other part is O(N2),
then their sum is O(N + N2). However, in this case we know that N2 will
dominate. So intuitively the maximum of the two will be a better bound.
● In some other cases, you will need to multiply the two functions; for example,
you are in a loop, which iterates O(N) times, and inside this loop is the body
which is O(N2), then the result is O(N × N2) = O(N3) .

15
Mathematical Background

● Rule 2: If T(N) is a polynomial of degree k, then T(N) = Θ(Nk).

● Rule 3: logk N = O(N) for any constant k.

This tells us that logarithms grow very slowly.

● Using these rules, we can arrange most of the common functions by their
growth rate.

16
Mathematical Background

17
Mathematical Background

● It is very bad style to include constants or low-order terms inside a Big-Oh.

● Do not say T(N) = O(2N2) or O(N2 + N).
● In both cases, the correct form is T(N) = O(N2).
● This means that in any analysis that will require a Big-Oh answer, all sorts of
shortcuts are possible.
● Lower-order terms can generally be ignored, and constants can be thrown
away.
● Considerably less precision is required in these cases.

18
Mathematical Background

● We can always determine the relative growth rates of two functions f(N) and
g(N) by computing limN→∞ f(N)/g(N), using L’Hôpital’s rule. The limit can
have four possible values:
○ The limit is 0: This means that f(N) = o(g(N))
○ The limit is c ≠ 0: This means that f(N) = Θ(g(N))
○ The limit is ∞: This means that g(N) = o(f(N))
○ The limit does not exist: there is no relation (this will not happen in our context).

19
Mathematical Background

● Usually, the relation between f(N) and g(N) can be derived by simple algebra.
● If f(N) = N logN and g(N) = N1.5, then to decide which of f(N) and g(N)
grows faster, one really needs to determine which of logN and N0.5 grows
faster.
● This is like determining which of log2N or N grows faster, but we know that N
grows faster than any power of a log.
● Thus, g(N) grows faster than f(N).

20
Mathematical Background

● It is bad to say f(N) ≤ O(g(N)) because the inequality is implied by the

definition.

● It is wrong to write f(N) ≥ O(g(N)) which does not make sense.

21
Model

● Now that we have discussed the mathematical background, let us talk about
our formal framework: model of computation.
● We cannot base the model on a specific hardware; so, we generalize it as
follows.
● Our model is basically a normal computer, in which instructions are executed sequentially.
● Our model has the standard repertoire of simple instructions: addition, multiplication,
comparison, and assignment, but, unlike the case with real computers, it takes exactly one
time unit to do anything simple.
● We also assume that our model has fixed-size integers and there are no fancy operations,
such as matrix inversion or sorting, that clearly cannot be done in one time unit.
● We also assume infinite memory.

22
Model

● This model has some weaknesses.

● In real life, not all operations take exactly the same time.
● For example, in our model, one disk read counts the same as an addition,
even though the addition is typically several orders of magnitude faster.
● Also, by assuming infinite memory, we ignore the fact that the cost of a
memory access can increase when slower memory is used due to larger
memory requirements.

23
What to Analyze?

● The most important resource to analyze is generally the running time.

● Several factors affect the running time of a program; such as the compiler and
the computer used. But these are ignored, and the input is taken as the main
consideration.
● We define two functions: Tavg(N) and Tworst(N) as the average and worst-
case running time used by an algorithm on input of size N.
● The details of the programming language do not affect a Big-Oh answer. It is
the algorithm that is analyzed, not the program (or the implementation).

24
Maximum Subsequence Sum Problem

● Given (possibly negative) integers A1,A2, . . . ,AN, find the maximum value of

● For convenience, the maximum subsequence sum is 0 if all integers are

negative.
● For example, for input −2, 11,−4, 13,−5,−2, the answer is 20, (A2 through A4).
● There are several algorithms that can solve this problem.
● In the next slide, their running time on a computer is given.

25
Maximum Subsequence Sum Problem

26
Maximum Subsequence Sum Problem

● For small amount of input, the algorithms all run in the blink of an eye, so if
only a small amount of input is expected, it might be silly to expend a great
deal of effort to design a clever algorithm.
● The times given do not include the time required to read the input.
● Reading data is generally the bottleneck; once the data are read, the
problem can be solved quickly.
● Check if the running time is proportional to the input size.

27
Maximum Subsequence Sum Problem

● The axes are not to scale; this makes the algorithm 3 seem like linear, and
algorithm 4 to be constant.

28
Maximum Subsequence Sum Problem

● A plot using larger values illustrates how the running time affects the running
time.

29
Running Time Calculations

● The previous table was obtained empirically, that is, it has been created by
actually running the algorithm and timing it, as in an experiment.
● There are several other ways to estimate the running time of a program.
● These methods are useful, because they also provide an insight into
designing efficient algorithms.
● We will be computing the Big-Oh running time.
● Since Big-Oh is an upper bound, we guarantee that the program will
terminate within a certain time period. It may stop earlier, but never later.

30
A Simple Example

● Here is a simple program to calculate . The analysis is simple.

31
A Simple Example
● Lines 4 and 7 count for one unit time each.
● Line 6 counts for four units per time executed (two multiplications, one addition,
and one assignment), and is executed n times, for a total of 4n units.

1;

32
A Simple Example
● Line 5 has hidden costs of initializing i, testing i ≤ n, and incrementing i. The total
cost of all these is 1 to initialize, n + 1 for all the tests, and n for all the
increments, which is 2n + 2.
● We ignore the costs of calling the method and returning, for a total of 6n + 4, thus
we say that this method is O(n).

33
A Simple Example

● If we have to perform all this work every time we need to analyze a program,
the task would quickly become infeasible.
● Fortunately, since we are giving the answer in terms of Big-Oh, there are lots
of shortcuts that can be taken without affecting the final answer.
● For example, line 6 is obviously an O(1) statement, so it is not really required
to count precisely. Same goes for line 4, which is insignificant compared with
the for loop.

34
General Rules

Rule 1 - for loops: The running time of a for loop is at most the running time of
the statements inside the for loop (including tests) times the number of iterations.

<

35
General Rules
Rule 2 - Nested loops: The total running time of a statement inside a group of nested
loops is the running time of the statement multiplied by the product of the sizes of all
the loops.
The following program is O(n2).

36
General Rules

Rule 3 - Consecutive Statements: These just add, as we have discussed in the

rules earlier.

As an example, the code below has O(n) followed by O(n2), so in total, it is O(n2).

37
General Rules
Rule 4 - if/else: For the fragment
if (condition)
S1
else
S2
● the running time of an if/else statement is never more than the running time of
the test plus the larger of the running times of S1 and S2.
● Clearly, this can be an overestimate in some cases, but it is never an
underestimate.

38
General Rules
● Other rules are obvious, but a basic strategy of analyzing from the inside (or
deepest part) out works.
● If there are method calls, these must be analyzed first.
● If there are recursive methods, there are several options.
● If the recursion is really just a thinly veiled for loop, the analysis is usually
trivial.
The following is O(n).

39
General Rules
● When recursion is properly used, it is difficult to convert the recursion into a
simple loop structure.
● In that case, the analysis will involve a recurrence relation that needs to be
solved.
● Consider the following program.
● Even though it looks like a clever use of recursion, for values of n around 40,
the algorithm becomes terribly inefficient.

40
General Rules
● Let T(n) be the running time for the method call fib(n).
● For n = 0 or n = 1, the running time is constant: T(0) = T(1) = 1.
● For n ≥ 2, the time to execute the method is the constant work at line 2, plus
the work at line 5.
● Line 5 contains an addition and two method calls which must be analyzed by
themselves.

41
General Rules

● The call to fib(n-1) requires T(n − 1), and fib(n-2) requires T(n − 2) units of
time.
● The total time required is then T(n − 1) + T(n − 2) + 2, with 2 for the
conditional test and the addition.
● So for n ≥ 2, we have the following formula
T(n) = T(n − 1) + T(n − 2) + 2

42
General Rules

● For n > 4, T(n) ≥ fib(n) ≥ (3/2)n

● The problem with this is that this program grows exponentially.
● There is a lot of redundant (unnecessarily repeated) work.
● fib(n-1) has already computed fib(n-2), but it is calculated again and again
violating 4th rule of recursion (compound interest rule).
● We try to stay away from exponential algorithms whenever possible.

43
Homework Assignments

● 2.1, 2.2, 2.3, 2.4, 2.5, 2.7, 2.11, 2.12

● 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.

44
References

● CE221 Lecture Slides by Prof. Dr. Cem Evrendilek

● Data Structures and Algorithm Analysis in Java, Third Edition, Mark Allen
Weiss
● Edited by Assoc. Prof. Dr. Kaya Oğuz

45