Discrete Mathematics for Computer Science

(^316) CHAPTER 5 Analysis of Algorithms

10. Suppose somebody manages to prove that the time taken by some frequently used
    algorithm is in O(nn ). Why is this probably uninteresting information?


11. What is the output of each of the following blocks of code?
    (a) cntr 0
    for i 0 to N
    cntr = cntr + 1
    print cntr
    (b) cntr 0
    for = 0 to N

for j = 0 to N

cntr = cntr + 1

print cntr

(c) cntr = 0

fori =0 toN

for j = i to N

fork = j to N

cntr = cntr + 1

print cntr

U Uncomputability

In the first half of the twentieth century, a group of mathematicians set out to formalize the

notion of a function being computable by an algorithm. Of particular concern was identi-

fying which functions, in principle, are computable and which are not. For this research,

the idea of an algorithm was not what could be done on a computer. In fact, much of this

work was done before the first modem computer was built! Rather, the idea of an algorithm

was what a person could do with paper and pencil by following rules in a mechanical fash-

ion. The research was motivated in part by mathematicians who conjectured that maybe

no algorithms exist to solve certain problems. If one wants to argue that no algorithm ex-

ists, then one must have some formal way to talk about the set of all algorithms. Standard

examples of algorithms included operations such as multiplication and long division.

Several formalisms were proposed. Each arguably captures the intuition of the term

algorithm. Perhaps the most important point is that although, on the surface, they present

very different notions of what an algorithm is, it has been proven that all the major for-

malisms define exactly the same class of functions that are computable by algorithms.

The widely accepted philosophical statement that these models do, indeed, exactly capture

the intuition of the expression "computable by an algorithm" is called Church's thesis. We

shall not discuss these models here. Instead, we shall present an informal definition that we

expect to be more accessible. (Of course, it is certainly also very revealing to examine the

classical models, and that is normally expected in any formal treatment of computability

theory.)

One basic assumption of "in principle computable" is that there should be no limita-

tions on resources. There are no time limits: The computer just keeps calculating until it

is done. There are no memory restrictions: Whenever the computer needs more memory,

it asks for it and gets it. In most current languages, by adding the properties of unlim-