Measuring complexitySlide 2What are the time complexities f(n) of:Asymptotic analysisThe definitions of big-O and small-oHow Big-O interacts with polynomial functionsHow big-O interacts with logarithmsMore on big-OSmall-o revisitedExamples on small-oTime complexity classesThe O(n2) time machine for {0k1k | k0}An O(n log n) time machine for {0k1k | k0}An O(n) time two-tape machine for {0k1k | k0}Single-tape vs. multitape machinesDefinition of time complexity for nondeterministic machinesDeterministic vs. nondeterministic machinesMeasuring complexityMeasuring complexitySection 7.1 Giorgi Japaridze Theory of ComputabilityMeasuring complexity7.1.aGiorgi Japaridze Theory of ComputabilityDefinition 7.1 Let M be a deterministic TM that halts for every input.The running time or time complexity of M is the function f: N N, where f(n) is the maximum number of steps that M uses on any input of length n. If f(n) is the time complexity of M, we say that M runs in time f(n), or that M is an f(n) time machine. Customarily we use n to represent the length of the input. If the time complexity of M is f(n) = n2+2, at most how many steps would M take to accept or reject the following strings? 01001001What are the time complexities f(n) of:7.1.bGiorgi Japaridze Theory of Computability1. The fastest machine that decides {w | w starts with a 0}?2. The fastest machine that decides {w | w ends with a 0}?3. The following machine M1, deciding the language {0k1k | k0}:M1 = “On input string w: 1. Scan across the tape and reject if a 0 is found to the right of a 1. 2. Repeat if both 0s and 1s remain on the tape: 3. Scan across the tape, crossing off a single 0 and a single 1. 4. If 0s still remain after all the 1s have been crossed off, or if 1s still remain after all the 0s have been crossed off, reject. Otherwise, if neither 0s nor 1s remain on the tape, accept.” Here we are lazy to try to figure out the exact values of the constants a, b, c (though, apparently b=1). But are those constants really all that important once we know that n2 is involved?Asymptotic analysis7.1.cGiorgi Japaridze Theory of Computability The exact running time of an algorithm often is a complex expression and depends on implementation and model details such as the number of states, the number of tape symbols, whether the “stay put” option is allowed, etc. Therefore, we usually just estimate time complexity, considering only “very large” inputs and disregarding constant factors. This sort of estimation is called asymptotic analysis. It is insensitive with respect to the above minor technical variations. E.g., if the running time is f(n) = 6n3+2n2+20n+45 (n --- the length of input), on large n’s the first term dominates all other terms, in the sense that 2n2+20n+45 is less than n3, so that 6n3 < f(n) < 7n3. And, as we do not care about constant factors (which is something between 6 and 7), after disregarding it we are left with just n3, i.e. the highest of the orders of the terms. We express the above by using the asymptotic notation or big-O notation, writing f(n) = O(n3). Intuitively, O can be seen as a suppressed constant, and the expression f(n) = O(n3) as saying that, on large inputs, f(n) does not exceed n3 by more than some constant factor. The small-o notation: f(n) = o(n4) intuitively means that, on large inputs, f(n) gets smaller (and smaller) compared with n4 --- smaller by more than any given constant factor.The definitions of big-O and small-o7.1.dGiorgi Japaridze Theory of ComputabilityDefinition 7.2 Let f and g be functions f,g: NR+. Say that f(n) = O(g(n)) iff positive integers c and n0 exists such that for every integer nn0, f(n)  cg(n).When f(n) = O(g(n)), we say that g(n) is an asymptotic upper bound for f(n). N means natural numbers, R+ means positive real numbersDefinition 7.5 Let f and g be functions f,g: NR+. Say that f(n) = o(g(n)) iff for every positive real number c, a number n0 exists such that for every integer nn0, f(n) < cg(n).In other words, lim = 0.n  f(n)g(n)We always have f(n)=O(f(n)) while never f(n)=o(f(n))! Our focus will mainly be on O.Intuition: “The complexity f(n) is  the complexity g(n)”.Intuition: “The complexity f(n) is < the complexity g(n)”.How Big-O interacts with polynomial functions7.1.eGiorgi Japaridze Theory of Computabilityf(n) = O(g(n)) iff there are c and n0 such that, for every nn0, f(n)  cg(n).f(n) = O(f(n)): pick c = n0=3f(n) = O(f(n)): pick c = n0=5n+10 = O(n): pick c = n0=3n2+4n+2 = O(n2): pick c = n0=Generally, bdnd + bd-1nd-1 + … + b2n2 + b1n + b0 = O(nd)How big-O interacts with logarithms7.1.fGiorgi Japaridze Theory of Computabilityf(n) = O(g(n)) iff there are c and n0 such that, for every nn0, f(n)  cg(n).log8 n = O(log2 n): pick c = n0=Remember that logb n = log2 n / log2 b = (1/log2 b) * log2 nlog2 n = O(log8 n): pick c = n0=Hence, in asymptotic analysis, we can simply write log n without specifying the base.Remember that log nc = c log n Hence log nc =Since log cn = n log c and c is a constant, we have log cn =Generally, log cf(n) =More on big-O7.1.gGiorgi Japaridze Theory of ComputabilityBig-O notation also appears in expressions such as f(n)=O(n2)+O(n). Here each occurrence of O represents a different suppressed constant. Because the O(n2) termdominates the O(n) term, we have O(n2)+O(n) = O(n2). Such bounds nc (c0) are called polynomial bounds. When O occurs in an exponent, as in f(n) = 2O(n), the same idea applies. This expression represents an upper bound of 2cn for some (suppressed) constant c.In other words, this is the bound dn for some (suppressed) constant d (d=2c).Such bounds dn, or more generally 2(n) where  is a positive real number, are called exponential bounds. Sometimes you may see the expression f(n) = 2O(log n). Using the identity n=2log n and thus nc=2c log n, we see that 2O(log n) represents an upper bound of nc for some c. The expression nO(1) represents the same bound in a different way, because O(1) represents a value that is never more than a fixed constant.Small-o revisited7.1.hGiorgi Japaridze Theory of ComputabilityDefinition 7.5 Let f and g be functions f,g: NR+. Say that f(n) = o(g(n)) iff for every positive real number c,