Basics of Algorithm Analysis

Question 1

Definition of Efficiency when evaluating algorithms?

Answer 1

Proposed Definition of Efficiency (1): An algorithm is efficient if, when implemented, it runs quickly on real input instances.

Proposed Definition of Efficiency (2): An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search.

Proposed Definition of Efficiency (3)” An algorithm is efficient if it has a polynomial running time.

Question 2

Define polynomial running time, or that it is a polynomial-time algorithm

Answer 2

There are absolute constants c > 0 and d > 0 so that on every input instance of size N, its running time is bounded by cNd primitive computational steps.

Ex:

• If the input size increases from N to 2N, the bound on the running time increases from cN^d to c(2N)^d = c. 2^dN^d

Question 3

Asymptotic Order of Growth

an algorithm’s worst-case running time on inputs of size n grows at a rate that is at most proportiona! to some function f(n).

The function f(n) then becomes a bound on the running
time of the algorithm

When we seek to say something about the running time of an algorithm on inputs of size n, one thing we could aim for would be a very concrete statement such as,

• “On any input of size n, the algorithm runs for at most 1.62n2 + 3.5n + 8 steps.”

What are the short-comming of this approach?

Answer 3

• First, getting such a precise bound may be an exhausting activity, and more detail than we wanted anyway.
• Second, because our ultimate goal is to identify broad classes of algorithms that have similar behavior, we’d actually like to classify running times at a coarser level of granularity so that similarities among different algorithms, and among different problems, show up more clearly.
• Finally, extremely detailestatements about the number of steps an algorithm executes are oftene–meaningless

Question 4

Asymptotic Upper Bounds

Answer 4

• T(n) be a function–say, [he worst-case running time of a certain algorithm on an input of size
• Given another function f(n), we say that T(n) is O(f(n)) (read as “T(n) is order f(n)”) if, for sufficiently large n, the function T(n) is bounded above by a constant multiple of f(n).
• More precisely, T(n) is O(f(n)) if there exist constants c > 0 and n_o >_ 0 so that for all n >_ no, we have T(n) <_ c. f(n). In

Question 5

Ex: Asymptotic Upper Bounds

just argued that

T(n) <_ (p + q + r)n²,

and since we also have n² < n³, we can conclude that T(n) < (p + q + r)n³ as the definition of O(n³) requires

Answer 5

Consider an algorithm whose running time has the form

T(n) = pn² + qn + r

for positive constants p, q, and r. We’d like to claim that any such function is O(n2).

To see why, we notice that for all n > 1, we have

qn < qn² and r < rn².

So we can write: T(n) =

pn~ + qn + r < pn² + qn² rn² = (p + q + r)n²

for all n >_ 1.

This inequality is exactly what the definition of O(-) requires:
** T(n) < cn², where c =p + q + r.**

Question 6

Asymptotic Lower Bounds

Answer 6

we want to express the notion that for arbitrarily large input sizes n, the function T(n) is at least a constant multiple of some specific function f(n).

Thus, we say that T(n) is ~Omaga(f(n)) if there exist constants ç > 0 and n_o _> 0 so that for all n > n₀, we have T(n) >= .ç * f(n).

Question 7

Asymptotic Lower Bounds

Answer 7

the function T(n) = pn² + qn + r, where p, q, and r are positive constants
let’s claim that T(n) = Omaga (n²⁾. Whereas establishing the upper bound involved “inflating” the terms in T(n) until it looked like a constant times n²,

we need to reduce the terms in T(n) until it looks like
a constant times n² such that for all n >= O, we have**: **

T(n) = pn² + qn + r > pn²,

which meets what is required by the definition of Omaga(.) with ç = p > 0.