Ch.4

Question 1

Counting Primitive Operations
To analyze the running time of an algorithm without performing experiments, we
perform an analysis directly on a high-level description of the algorithm (either in the form of an actual code fragment, or language-independent pseudocode). We
define a set of [p..e o..s] such as the following…

Answer 1

[primitive operations] 154

Question 2

An algorithm may run faster on some inputs than it does on others of the same size.
Thus, we may wish to express the running time of an algorithm as the function of
the input size obtained by taking the average over all possible inputs of the same
size. Unfortunately, such an [a..e-c..e] analysis is typically quite challenging.
It requires us to define a probability distribution on the set of inputs, which is often
a difficult task. Figure 4.2 schematically…

Answer 2

[average-case] 155

Question 3

The Constant Function
The simplest function we can think of is the [c..t f..n], that is,
f (n) = c,
for some fixed constant c, such as c = 5, c = 27, or c = 210. That is, for any argument n, the constant function f (n) assigns the value c. In other words, it does
not matter what the value of n is; f (n) will a

Answer 3

[constant function] 156