Equations Speak Louder Than Words
We have thus far created a strong link between familiar intuition and formal mathematics, with the intent of constructing a framework with which to better analyse and understand the complexity of computations. We continue on this trajectory by classifying decision problems according to the resources they consume on deterministic (for the same input, will always produce the same output on different runs) and non-deterministic (for the same input, can produce different outputs on different runs) Turing machines. Our resource of consideration will be time, T(n), called time complexity, where n is input length. A similar analysis can be done for space or memory.
Definition 4.1 Let T(n): N → N (T(n)‘s domain and codomain is the set of Naturals) be a proper time function. Then DTIME(T(n)) is the time complexity class containing languages that can be recognized by deterministic Turing machines (DTM’s) that halt on all inputs in time T(n), where n is the length of an input.
For constant k > 0, and input size n ≥ 1, DTIME(nk) is an example of a complexity class consisting of all decision problems solvable by a deterministic Turing machine in polynomial time nk. Since time on a Turing machine is measured by the number of steps, we can say that time for a given DTM can be reduced by a constant factor by modifying the Turing machine description so that it acts on larger units of information. Simply put, for a constant K > 0 the classes DTIME(nk) and DTIME(Knk) are equivalent.
We define complexity class P, one of the most important complexity classes, as follows.
Definition 4.2 The class P is the set of decision problems solvable in polynomial time on DTM’s; it is defined as:
P ∪k≥0 DTIME(nk)
For each decision problem P’ ∈ P there is a DTM M and a polynomial p(n) such that M halts on each input string of length n in p(n) steps, accepting this string if it is an instance ω of P’ and rejecting it otherwise.
This is equivalent to saying there is an algorithm that can solve problem P’ in polynomial time.
Problems in P are considered feasible because they can be decided in time polynomial in the length of their input. Thus, theoretically, problems such as n1000 are considered feasible even though they grow rapidly as n increases. Problems that grow exponentially as n increases are considered infeasible.
The next category consists of non-deterministic polynomial time problems, also referred to as NP problems. For completeness we begin by giving a definition for class NP.
Definition 4.3 Let T(n): N → N be a proper time function. Then
NTIME(T(n)) is the time complexity class containing languages that can be recognized by non-deterministic Turing machines (NDTM’s) that halt on all inputs in time T(n), where n is the length of an input.
For constant k > 0, and input size n ≥ 1, NTIME(nk) is an example of a complexity class consisting of all decision problems solvable by a nondeterministic Turing machine in nk polynomial time. Again, time on a Turing machine is measured by the number of steps, therefore a given NDTM can be reduced by a constant factor by modifying its description so that it acts on larger units of information, for K ≥ 0, NTIME(nk) is the same as NTIME(Knk).
Definition 4.4 The class NP is the set of decision problems solvable in polynomial time on NDTM’s; it is defined as:
NP ∪k≥0 NTIME(nk)
For each decision problem P’ ∈ NP there is an NDTM M and a polynomial p(n) such that for each instance ω of P’, |ω| = n, there is a witness string input of length n such that M accepts ω in p(n) steps. It seems infeasible to find a solution, but if we guess one, we can verify that it is indeed a solution in polynomial time. So the key observation is that solving a problem with a NDTM in polynomial time is equivalent to verifying a solution with a DTM in polynomial time.
As it turns out, many important practical problems are in fact in NP. If P is equal to NP, then all problems in NP can be solved efficiently. If not, then some such problems (in particular those that are NP-complete) require superpolynomial time and are largely infeasable. The question of whether P = NP remains open, in spite of many attempts to obtain a decisive answer. As such, the feasibility of problems in NP is unknown.
The next complexity category we want to consider is the class of deterministic
exponential time problems.
Definition 4.5 The class EXPTIME is equal to the set of decision problems solvable in exponential time on DTM’s; it is defined as:
EXPTIME ∪k≥0 DTIME(2nk)
Theorem 4.6 (Time hierarchy theorem) If f, g: N → N are time-constructible functions such that f(n)logf(n) = o(g(n)), then DTIME(f) ⊂ DTIME(g).
Informally, the theorem assures us that given more time, a Turing machine can solve more problems. We can say, for example, there are problems that can be solved in n2 time but not in n time.
Theorem 4.7 The following complexity class containments hold:
P ⊆ NP ⊆ EXPTIME, with P ⊂ EXPTIME
We will consider other complexity classes at a later stage, these are adequate as a starting point.
Asymptotic representation of Time Complexity
We now introduce Big-oh notation. T(n) will often give us some function in n of the form c0nk + c1nk-1 + c2nk-2 + … + ckn0, where ci, i = 1, 2, 3, … is a constant and k ∈ R. As n gets larger, the term with the highest order in T(n) will dominate its value, so that all other terms count for less and less. For example, suppose T(n) = 3n3 + 5n2 + 2n + 5, when n is 1000, the term 3n3 will be more than 500 times greater than the remaining terms 5n2 + 2n + 5. So for large enough values of n, the term with the highest order of magnitude becomes larger than the remaining terms and ultimately determines the overall behavior of the function. In the example above, the dominant term is 3n3. However small the coefficient of the dominant term may be, there is a large enough n to overcome the total of less significant terms. By dropping the constant coefficients and less significant terms, we focus on the algorithm’s growth rate. We say T(n) = 3n3 + 5n2 + 2n + 5 = O(n3). This is what is termed asymptotic notation, it expresses the behavior of T(n) for large values of n. Other forms of asymptotic notation are o(g(n)), Ω(g(n)), ω(g(n)), and Θ(g(n)).
Generally, O(g(n)) is the set of all functions with at most the same order
of growth as g(n). For example O(n3) = {n3, 2n3 + 5n2 + 2n + 5, 1000n2 + n, n, log n,…}. Formally, we define O(g(n)) as:
O(g(n)) = {f(n)|∃C > 0, n0 ≥ 1, such that ∀n ≥ n0, 0 ≤ f(n) ≤ C ∗ g(n)}
If f(n) = O(g(n)), then limn→∞f(n)/g(n) = c, 0 ≤ c < ∞
Generally, o(g(n)), called little-oh, is the set of all functions with a smaller rate of growth than g(n). For example o(n3) = {n2, 5n2 + 2n + 5, 1000n2 + n, n, log n,…}. Note n3 !∈ n3. Formally, we define o(g(n)) as a set as follows:
o(g(n)) = {f(n)|∀C > 0, ∃n0 ≥ 1, such that ∀n ≥ n0, 0 ≤ f(n) < C ∗ g(n)}
If f(n) = o(g(n)), then limn→∞f(n)/g(n) = 0
We also introduce , Ω(g(n)), called big omega, which is the set of all functions with at least
the same order of growth as g(n). For example Ω(n3) = {n3, 2n4 + 5n5 + 3n +5, 6n6 + n, 2n, n!, …}. Formally, we define Ω(g(n)) as follows:
Ω(g(n)) = {f(n)|∃C > 0, n0 ≥ 1, such that ∀n ≥ n0, 0 ≤ C ∗ g(n) ≤ f(n)}
If f(n) = Ω(g(n)), then limn→∞f(n)/g(n) = c, 0 < c ≤ ∞
Consequently, we have ω(g(n)), called little omega, which is the set of all functions with a higher growth rate than g(n). For example ω(n3) = {2n4 + 5n5 + 3n + 5, 6n6 +n, 2n, n!, …}. Note, n3 !∈ ω(n3). Formally, we define ω(g(n)) as:
ω(g(n)) = {f(n)|∀C > 0, ∃n0 ≥ 1, such that ∀n ≥ n0, 0 ≤ C ∗ g(n) < f(n)}
If f(n) = ω(g(n)), then limn→∞f(n)/g(n) = ∞
Last but not least, we consider Θ(g(n)), called theta of g(n), also known as asymptotically tight bound, which is the set of all functions with the same order of growth as g(n). For example Θ(n3) = {n3, 2n3 + 5n2 + 3n + 5, , 7n3, …}. Formally, we define Θ(g(n)) as follows:
Θ(g(n)) = {f(n)|∃C1, C2 > 0, n0 ≥ 1, such that ∀n ≥ n0, 0 ≤ C1∗g(n) ≤ f(n) ≤ C2∗g(n)}
If f(n) = Θ(g(n)), then limn→∞f(n)/g(n) = c, 0 < c < ∞
NOTE 1 If f(n) = Θ(g(n)), then f(n) = Ω(g(n)) and f(n) = O(g(n)), because f = g ⇔ f ≥ g ∧ f ≤ g.
NOTE 2 If f(n) = O(g(n)), then g(n) = Ω(f(n))
What is the significance of this notation? As shown above, O gives a set of upper bounds and Ω a set of lower bounds. We are interested in the tightest bounds. Note that Θ gives the tightest upper and lower bounds, which makes it a good starting point for assessing T(n)‘s growth. O gives the worst case running time, meaning an algorithm will not perform worse than that for any input size; and Ω gives the best case running time, meaning the algorithm will not perform better than that for any input size. If O and Ω are the same, we use Θ, which gives average running time. If they are not, we are more interested in the worst case running time. Consider an algorithm A that performs a sequential search of an element i in an array ARRAY[.] of n elements. A‘s best case time will occur if i is the first element in ARRAY[.], because A does only one comparison, best case time is Ω(1). A‘s worst case running time is if element i is not in ARRAY[.] because the algorithm does n comparisons, so worst case running time is O(n); A takes n steps to complete its task. The average time will be Θ(n/2) which is Θ(n), so for this example we don’t use Θ. O(n) is the most informative measure of A‘s performance on ARRAY[.] as n gets larger.
In the next post we consider the complexity class O(n) more closely.
Leave a Reply