3.2. Complexity Issues

Given an algorithm (or an implementation of the same), the time and space required for the execution of the algorithm on a machine depend very much on the machine’s architecture and on the compiler. But this does not mean that we cannot make some general theoretical estimates. The so-called asymptotic estimates that we are going to introduce now tend to approach the real situation as the input size tends to infinity. For finite input sizes (which is always the case in practice), these theoretical predictions turn out to provide valuable guidelines.

3.2.1. Order Notations

We start with the following important definitions.

Definition 3.1.

Let f and g be positive real-valued functions of natural numbers.

  1. f is said to be bounded above by g or of the order of g, denoted f = O(g), if there exists an and a positive real constant c such that f(n) ≤ cg(n) for all n ≥ n0. In this case, we also say that g is bounded below by f and denote this by g = Ω(f).

  2. If f = O(g) and g = O(f), we say that f and g are of the same order and denote this by f = Θ(g) (or by g = Θ(f)). Equivalently, f = Θ(g) if and only if f = O(g) and f = Ω(g); that is, if and only if there exist an integer and real positive constants c1, c2 such that c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0.

  3. f is said to be of strictly lower order than g, denoted f = o(g), if f(n)/g(n) tends to 0 as n tends to infinity. In other words, f = o(g) if and only if for every real positive constant c (however small it may be) there exists an integer such that f(n) < cg(n) for all n ≥ nc. If f = o(g), we also say that g is of strictly higher order than f and denote this by g = ω(f). Thus g = ω(f) if and only if for every real positive constant c (however large it may be) there exists an integer such that g(n) > cf(n) for all n ≥ nc.

Example 3.1.

  1. Let f(n) := adnd + · · · + a1n + a0 with d ≥ 0, , ad > 0. Then f = Θ(nd). This heuristically means that as n becomes sufficiently large, the leading term adnd dominates over the other terms, and apart from the constant of proportionality ad the function f(n) grows with n as nd does. If f = Θ(nd) for some integer d > 0, we say that f is of polynomial order in n.[1] A Θ(1) function is often called a constant function.

    [1] This is not the complete truth. Functions like , n2.3 or n3(log n)2 would be better included in the polynomial family. Thus, we may define f to be of polynomial order (in n), if f = O(nd) and f = Ω(nd′) for some positive real constants d, d′. Similar comments hold for poly-logarithmic and exponential orders.

  2. If f = Θ((log n)a) for some real a > 0, we say that f is of poly-logarithmic order in n. By Exercise 3.2(b), any function of poly-logarithmic order grows asymptotically slower than any function of polynomial order.

  3. If f = Θ(an) for some real a > 1, f said to be of exponential order in n. Again by Exercise 3.2(b) any function of exponential order grows asymptotically faster than any function of polynomial order.

  4. Now, consider a function of the form

    Equation 3.1


    for real c > 0 and for 0 ≤ α ≤ 1. For α = 0, we have f = Θ(nc); that is, f is of polynomial order. On the other extreme, if α = 1, f = Θ(an), where a := exp(c), that is, f is of exponential order. If 0 < α < 1, we say that f is of subexponential order in n, since the order of f is somewhere in between polynomial and exponential. We will come across functions of subexponential orders quite frequently in the rest of the book. Note that as α increases from 0 to 1, the order of f also increases monotonically from polynomial to exponential.

  5. A function f = O(na(log n)b) with a > 0 and b ≥ 0 is often denoted by the soft O-notation: f = O~(na). This implies that up to multiplication by a polynomial in log n the function f is of the order of na. Similarly, if f = O(ang(n)) for a > 1 and for some g(n) of polynomial order, we say that f = O~(an). Intuitively spoken, the O-notation hides constant multipliers, whereas the soft O-notation suppresses exponentially small multipliers.

  6. The notion of order can be readily extended to functions with two or more input variables. For example, for positive real-valued functions f, g of two positive integer variables m, n one says f = O(g), if for some m0, and for some positive real constant c one has f(m, n) ≤ cg(m, n) for all m ≥ m0 and n ≥ n0. The function f(m, n) = m32n is of polynomial order in m, but of exponential order in n.

The order notation is used to analyse algorithms in the following way. For an algorithm, the input size is defined as the total number of bits needed to represent the input of the algorithm. We find asymptotic estimates of the running time and the memory requirement of the algorithm in terms of its input size. Let f(n) denote the running time[2] of an algorithm A for an input of size . If f(n) = Θ(na) (or, more generally, if f = O(na)) for some a > 0, A is called a polynomial-time algorithm. If a = 1 (resp. 2, 3, . . .), then A is specifically called a linear-time (resp. quadratic-time, cubic-time, . . .) algorithm. A Θ(1) algorithm is often called a constant-time algorithm. If f = Θ(bn) for some b > 1, A is called an exponential-time algorithm. Similarly, if f satisfies Equation (3.1) with 0 < α < 1, A is called a subexponential-time algorithm.

[2] The practical running time of an algorithm may vary widely depending on its implementation and also on the processor, the compiler and even on run-time conditions. Since we are talking about the order of growth of running times in relation to the input size, we neglect the constants of proportionality and so these variations are usually not a problem. If one plans to be more concrete, one may measure the running time by the number of bit operations needed by the algorithm.

One has similar classifications of an algorithm in terms of its space requirements, namely, polynomial-space, linear-space, exponential-space, and so on. We can afford to be lazy and drop -time from the adjectives introduced in the previous paragraph. Thus, an exponential algorithm is an exponential-time algorithm, not an exponential-space algorithm.

It is expedient to note here that the running time of an algorithm may depend on the particular instance of the input, even when the input size is kept fixed. For an example, see Exercise 3.3. We should, therefore, be prepared to distinguish, for a given algorithm and for a given input size n, between the best (that is, shortest) running time fb(n), the worst (that is, longest) running time fw(n), the average running time fa(n) on all possible inputs (of size n) and the expected running time fe(n) for a randomly chosen input (of size n). In typical situations, fw(n), fa(n) and fe(n) are of the same order, in which case we simply denote, by running time, one of these functions. If this is not the case, an unqualified use of the phrase running time would denote the worst running time fw(n).

The order notation, though apparently attractive and useful, has certain drawbacks. First it depicts the behaviour of functions (like running times) as the input size tends to infinity. In practice, one always has finite input sizes. One can check that if f(n) = n100 and g(n) = (1.01)n are the running times of two algorithms A and B respectively (for solving the same problem), then f(n) ≤ g(n) if and only if n = 1 or n ≥ 117,309. But then if the input size is only 1,000, one would prefer the exponential-time algorithm B over the polynomial-time algorithm A. Thus asymptotic estimates need not guarantee correct suggestions at practical ranges of interest. On the other hand, an algorithm which is a product of human intellect does not tend to have such extreme values for the parameters; that is, in a polynomial-time algorithm, the degree is usually ≤ 10 and the base for an exponential-time algorithm is usually not as close to 1 as 1.01 is. If we have f(n) = n5 and g(n) = 2n as the respective running times of the algorithms A and B, then A outperforms B (in terms of speed) for all n ≥ 23.

The second drawback of the order notation is that it suppresses the constant of proportionality; that is, an algorithm whose running time is 100n2 has the same order as one whose running time is n2. This is, however, a situation that we cannot neglect in practice. In particular, when we compare two different implementations of the same algorithm, the one with a smaller constant of proportionality is more desirable than the one with a larger constant. This is where implementation tricks prove to be important and even indispensable for large-scale applications.

3.2.2. Randomized Algorithms

A deterministic algorithm is one that always follows the same sequence of computations (and thereby produces the same output) for a given input. The deterministic running time of a computational problem P is the fastest of the running times (in order notation) of the known algorithms to solve P.

If an algorithm makes some random choices during execution, we call the algorithm randomized or probabilistic. The exact sequence of computations followed by the algorithm depends on these random choices and as a result different executions of the same algorithm may produce different outputs for a given input. At first glance, randomized algorithms look useless, because getting different outputs for a given input is apparently not what one would really want. But there are situations where this is desirable. For example, in an implementation of the RSA protocol, one generates random primes p and q of given bit lengths. Here we require our prime generation procedure to produce different primes during different executions (that is, for different entities on the net).

More importantly, randomized algorithms often provide practical computational solutions for many problems for which no practical deterministic algorithms are known. We will shortly encounter many such situations where randomized algorithms are simplest and/or fastest known algorithms. However, this sudden enhancement in performance by random choices does not come for free. To explain the so-called darker sides of randomization, we explain two different types of randomized algorithms.

A Monte Carlo algorithm is a randomized algorithm that may produce incorrect outputs. However, for such an algorithm to be useful, we require that the running time be always small and the probability of an error sufficiently low. A good example of a Monte Carlo algorithm is Miller–Rabin’s algorithm (Algorithm 3.13) for testing the primality of an integer. For an integer of bit size n, the Miller–Rabin test with t iterations runs in time O(tn3). Whenever the algorithm outputs false, it is always correct. But an answer of true is incorrect with an error probability ≤ 2–2t, that is, it certifies a composite integer as a prime with probability ≤ 2–2t. For t = 20, an error is expected to occur less than once in every 1012 executions. With this little sacrifice we achieve a running time of O(n3) (for a fixed t), whereas the best deterministic primality testing algorithm (known to the authors at the time of writing this book) takes time O(n7.5) and hence is not practical.

A Las Vegas algorithm is a randomized algorithm which always produces the correct output. However the running time of such an algorithm depends on the random choices made. For such an algorithm to be useful, we expect that for most random choices the running time is small. As an example, consider the problem of finding a random (monic) irreducible polynomial of degree n over . Algorithm 3.22 tests the irreducibility of a polynomial in in deterministic polynomial time. We generate random polynomials of degree n and check the irreducibility of these polynomials by Algorithm 3.22. From Section 2.9.2, we know that a randomly chosen monic polynomial of degree n over a finite field is irreducible with an approximate probability of 1/n. This implies that after O(n) random polynomials are tried, one expects to find an irreducible polynomial. The resulting Las Vegas algorithm (Algorithm 3.23) runs in expected polynomial time. It may, however, happen that for certain random choices we keep on generating reducible polynomials for an exponential number of times, but the likelihood of such an accident is very, very low (Exercise 3.5).

An algorithm is said to be a probabilistic or randomized polynomial-time algorithm, if it is either a Monte Carlo algorithm with polynomial worst running time or a Las Vegas algorithm with polynomial expected running time. Both the above examples of randomized algorithms are probabilistic polynomial-time algorithms. A combination of these two types of algorithms can also be conceived; namely, algorithms that produce correct outputs with high probability and have polynomial expected running time. Some computational problems are so challenging that even such probably correct and probably fast algorithms are quite welcome.

We finally note that there are certain computational problems for which the deterministic running time is exponential and for which randomization also does not help much. In some cases, we have subexponential randomized algorithms which are still too slow to be of reasonable practical use. Some of these so-called intractable problems are at the heart of the security of many public-key cryptographic protocols.

3.2.3. Reduction Between Computational Problems

In the last two sections, we have introduced theoretical measures (the order notations) for estimating the (known) difficulty of solving computational problems. In this section, we introduce another concept by which we can compare the relative difficulty of two computational problems.

Let P1 and P2 be two computational problems. We say that P1 is polynomial-time reducible to P2 and denote this as , if there is a polynomial-time algorithm which, given a solution of P2, provides a solution for P1. This means that if , then the problem P1 is no more difficult than P2 apart from the extra polynomial-time reduction effort. In that case, if we know an algorithm to solve P2 in polynomial time, then we have a polynomial-time algorithm for P1 too. If and , we say that the problems P1 and P2 are polynomial-time equivalent and write P1 ≅ P2.

In order to give an example of these concepts, we let G be a finite cyclic multiplicative group of order n and g a generator of G. The discrete logarithm problem (DLP) is the problem of computing for a given an integer x such that a = gx. The Diffie–Hellman problem (DHP), on the other hand, is the problem of computing gxy from the given values of gx and gy. If one can compute y from gy, one can also compute gxy = (gx)y by performing an exponentiation in the group G. Therefore, , if exponentiations in G can be computed in polynomial time. In other words, if a solution for DLP is known, a solution for DHP is also available: that is, DHP is no more difficult than DLP except for the additional exponentiation effort. However, the reverse implication (that is, whether ) is not known for many groups.

So far we have assumed that our reduction algorithms are deterministic. If we allow randomized (that is, probabilistic) polynomial-time reduction algorithms, we can similarly introduce the concepts of randomized polynomial-time reducibility and of randomized polynomial-time equivalence. We urge the reader to formulate the formal definitions for these concepts.

Exercise Set 3.2

3.1

  1. Sort the following functions in the increasing sequence of order. (Don’t mind if some of these functions are not defined for a few values of n.)

    1012, 2n, 22n, 2n2, 100n2, 10–3n3, 1/n, , n!, nn,

    log n, (log n)/n, n/log n, n2 log n, n(log n)2, (0.1)log n, (log n)n,

    1/log n, , 106(log n)100, log log n, 2log log n, nlog log n,

    , , ,

    exp(n1/3(ln n)2/3), exp((ln n)1/3(ln ln n)2/3).

  2. Evaluate the functions of Part (a) at n = 10i for i = 1, 2, . . . , 10 and conclude that as n gets larger, the asymptotic ordering tallies with the actual ordering more correctly.

3.2

  1. Show that for any real a > 1 and b > 0 one has nb = o(an).

  2. For any positive real c, d, show that (log n)c = o(nd).

  3. Show that if f = O(g) and g = O(h), then f = O(h).

  4. Give an example to show that f = O(g) does not necessarily imply f = Θ(g).

  5. Give an example of a function f with f = O(n1+ε) for every ε > 0, but f is not O(n).

3.3Suppose that an algorithm A takes as input a bit string and runs in time g(t), where t is the number of one-bits in the input string. Let fb(n), fw(n), fa(n) and fe(n) respectively denote the best, worst, average and expected running times of A for inputs of size n. Derive the following table under the assumption that each of the 2n bit strings of length n is equally likely.
  Running times 
g(t)fb(n)fw(n)fa(n)fe(n)
t0nn/2n/2
t20n2n(n + 1)/4n2/4
2t12n(3/2)n

3.4

  1. Show that an exponential-space (resp. subexponential-space) algorithm must be (at least) exponential-time (resp. subexponential-time) too. You may assume that at a time a computing device can access (read/write) at most a finite number of memory locations.

  2. Give an example of an algorithm that is exponential-time but polynomial-space.

3.5Consider the Las Vegas algorithm discussed in Section 3.2.2 for generating a random irreducible polynomial of degree n over . Assume that a randomly chosen polynomial in of degree n has (an exact) probability of 1/n for being irreducible. Find out the probability pr that r polynomials chosen randomly (with repetition) from are all reducible. For n = 1000, calculate the numerical values of pr for r = 10i, i = 1, . . . , 6, and find the smallest integers r for which pr ≤ 1/2 and pr ≤ 10–12. Find the expected number of polynomials tested for irreducibility, before the algorithm terminates.
3.6Let n = pq be the product of two distinct primes p and q. Show that factoring n is polynomial-time equivalent to computing φ(n) = (p–1)(q–1), where φ is Euler’s totient function. (Assume that an arithmetic operation (including computation of integer square roots) on integers of bit size t can be performed in polynomial time (in t).)
3.7Let G be a finite cyclic multiplicative group and let H be the subgroup of G generated by whose order is known. The generalized discrete logarithm problem (GDLP) is the following: Given , find out if and, if so, find an integer x for which a = hx. Show that GDLP ≅ DLP, if exponentiations in G can be carried out in polynomial time and if DLP in H is polynomial-time equivalent to DLP in G. [H]
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.144.232.189