Ch.11: Analysis of Algorithm Efficiency
Chapter 11 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 11.1. Real-Valued Functions of a Real Variable and Their Graphs 11.2. O-, Ω-, and Θ-Notations 11.3. Application: Analysis of Algorithm Efficiency I 11.4. Exponential and Logarithmic Functions: Graphs and Orders 11.5. Application: Analysis of Algorithm Efficiency II
148 flashcards · Mathematics · by lakesare
Part of Textbooks › Discrete Mathematics with Applications (Susanna Epp) · 12 courses
[Real-Valued Functions and Their Graphs] Who laid the foundation of analytic geometry, and where?
René Descartes, in the appendix "Geometry" of his "Discourse on Method" (1637). Analytic geometry studies algebraic objects (functions, equations, inequalities) with geometric methods and geometric objects (lines, circles, half-planes) with algebraic methods.
[Real-Valued Functions and Their Graphs] What is a Cartesian plane (two-dimensional Cartesian coordinate system)?
A picture of R×R\mathbb{R} \times \mathbb{R}R×R : a one-to-one correspondence between ordered pairs of real numbers and points of a plane. Two perpendicular axes, horizontal and vertical, meet at the origin. The pair (x,y)(x, y)(x,y) is the point ∣x∣|x|∣x∣ units right or left of the vertical axis and ∣y∣|y|∣y∣ units above or below the horizontal axis.Example: (−2,3)(-2, 3)(−2,3) is 2 units left of the vertical axis and 3 units above the horizontal axis.
[Real-Valued Functions and Their Graphs] What is a real-valued function of a real variable?
A function from one set of real numbers to another. So its domain and its co-domain are both sets of real numbers.Example: f(x)=x2f(x) = x^2f(x)=x2 for all real numbers xxx .
[Real-Valued Functions and Their Graphs] Let fff be a real-valued function of a real variable. What is the graph of fff ?
The set of all points (x,y)(x, y)(x,y) in the Cartesian plane with xxx in the domain of fff and y=f(x)y = f(x)y=f(x) . So (x,y)(x, y)(x,y) lies on the graph of fff if, and only if, y=f(x)y = f(x)y=f(x) , and f(x)f(x)f(x) is the height of the graph at xxx . Example: the graph of f(x)=x2f(x) = x^2f(x)=x2 contains (3,9)(3, 9)(3,9) but not (3,8)(3, 8)(3,8) .
[Real-Valued Functions and Their Graphs] Let aaa be a nonnegative real number. What is the power function with exponent aaa , written pap_apa ?
pa(x)=xa\boldsymbol{p_a(x) = x^a}pa(x)=xa for each nonnegative real number xxx . Computer science applications almost always need only nonnegative xxx and aaa , so the definition is restricted to these.Example: p1/2(9)=91/2=3p_{1/2}(9) = 9^{1/2} = 3p1/2(9)=91/2=3 .
[Real-Valued Functions and Their Graphs] So that p0(x)=x0=1p_0(x) = x^0 = 1p0(x)=x0=1 holds for every nonnegative xxx , the book defines 00=0^0 =00= 1.
Example: p0(0)=00=1p_0(0) = 0^0 = 1p0(0)=00=1 , so the graph of p0p_0p0 contains (0,1)(0, 1)(0,1) .
[Real-Valued Functions and Their Graphs] What are the graphs of the power functions p0p_0p0 , p1p_1p1 , p1/2p_{1/2}p1/2 and p2p_2p2 ?
p0p_0p0 : the horizontal half-line of height 1; p1p_1p1 : the half-line of slope 1 starting at (0,0)(0, 0)(0,0) ; p1/2p_{1/2}p1/2 and p2p_2p2 : the curves through the points (x,x)(x, \sqrt{x})(x,x) and (x,x2)(x, x^2)(x,x2) . Example: p1/2p_{1/2}p1/2 contains (0,0),(1,1),(4,2),(9,3)(0, 0), (1, 1), (4, 2), (9, 3)(0,0),(1,1),(4,2),(9,3) ; p2p_2p2 contains (0,0),(1,1),(2,4),(3,9)(0, 0), (1, 1), (2, 4), (3, 9)(0,0),(1,1),(2,4),(3,9) .
[Real-Valued Functions and Their Graphs] Order x1/2x^{1/2}x1/2 , xxx and x2x^2x2 from largest to smallest, once for 0<x<10 < x < 10<x<1 and once for x>1x > 1x>1 .
For 0<x<10 < x < 10<x<1 : x1/2>x>x2x^{1/2} > x > x^2x1/2>x>x2 . For x>1x > 1x>1 : x2>x>x1/2x^2 > x > x^{1/2}x2>x>x1/2 . All three graphs pass through (1,1)(1, 1)(1,1) .Example: x=14x = \frac14x=41 : 12>14>116\frac12 > \frac14 > \frac1{16}21>41>161 . x=4x = 4x=4 : 16>4>216 > 4 > 216>4>2 .
[Real-Valued Functions and Their Graphs] What is the floor ⌊x⌋\lfloor x \rfloor⌊x⌋ of a real number xxx ?
The greatest integer that is less than or equal to xxx , i.e. the unique integer nnn with n≤x<n+1n \le x < n + 1n≤x<n+1 . On the number line, the integer at xxx or immediately to the left of xxx .Example: ⌊2.7⌋=2\lfloor 2.7 \rfloor = 2⌊2.7⌋=2 , ⌊−2.7⌋=−3\lfloor -2.7 \rfloor = -3⌊−2.7⌋=−3 , ⌊5⌋=5\lfloor 5 \rfloor = 5⌊5⌋=5 .
[Real-Valued Functions and Their Graphs] What does the graph of the floor function F(x)=⌊x⌋F(x) = \lfloor x \rfloorF(x)=⌊x⌋ look like?
Horizontal segments like a staircase: on each interval n≤x<n+1n \le x < n + 1n≤x<n+1 ( nnn an integer) the height is nnn . The left end of each step is on the graph; the open circle at the right end is not. Example: F(1)=F(1.5)=1F(1) = F(1.5) = 1F(1)=F(1.5)=1 , but F(2)=2F(2) = 2F(2)=2 .
[Real-Valued Functions and Their Graphs] What is the ceiling ⌈x⌉\lceil x \rceil⌈x⌉ of a real number xxx ?
The least integer that is greater than or equal to xxx , i.e. the unique integer nnn with n−1<x≤nn - 1 < x \le nn−1<x≤n . Example: ⌈2.3⌉=3\lceil 2.3 \rceil = 3⌈2.3⌉=3 , ⌈−2.3⌉=−2\lceil -2.3 \rceil = -2⌈−2.3⌉=−2 , ⌈5⌉=5\lceil 5 \rceil = 5⌈5⌉=5 .
[Real-Valued Functions and Their Graphs] A formula defines a function on an interval of real numbers, and also a function on the integers in that interval. How do you get the graph of the second from the graph of the first?
Keep only the points of the first graph whose first coordinate is an integer. Example: p1(x)=xp_1(x) = xp1(x)=x for real x≥0x \ge 0x≥0 (a half-line), and f(n)=nf(n) = nf(n)=n for integers n≥0n \ge 0n≥0 (isolated points).
[Real-Valued Functions and Their Graphs] Let g(n)=n1/2g(n) = n^{1/2}g(n)=n1/2 for all nonnegative integers nnn . What does the graph of ggg look like?
Isolated points (n,n)(n, \sqrt{n})(n,n) , one above each nonnegative integer nnn , lying on the graph of p1/2p_{1/2}p1/2 . Example: (0,0),(1,1),(2,1.41),(3,1.73),(4,2)(0, 0), (1, 1), (2, 1.41), (3, 1.73), (4, 2)(0,0),(1,1),(2,1.41),(3,1.73),(4,2) .
[Real-Valued Functions and Their Graphs] Let fff be a real-valued function of a real variable and MMM a real number. What is the multiple of fff by MMM , written MfMfMf ?
The function with the same domain as fff defined by (Mf)(x)=M⋅f(x)(Mf)(x) = M \cdot f(x)(Mf)(x)=M⋅f(x) . So the height of the graph of MfMfMf at xxx is MMM times the height of the graph of fff at xxx .Example: for f(x)=x2f(x) = x^2f(x)=x2 , (3f)(2)=3⋅4=12(3f)(2) = 3 \cdot 4 = 12(3f)(2)=3⋅4=12 .
[Real-Valued Functions and Their Graphs] This is the graph of a function fff . What are the heights of the graph of 2f2f2f at x=−2x = -2x=−2 and at x=2x = 2x=2 , and how does the whole graph of 2f2f2f compare with that of fff ?
444 and −4-4−4 . Every height is multiplied by 2: the highs are twice as high and the lows twice as low. f(−2)=2f(-2) = 2f(−2)=2 and f(2)=−2f(2) = -2f(2)=−2 . Where f(x)=0f(x) = 0f(x)=0 , also (2f)(x)=0(2f)(x) = 0(2f)(x)=0 .
[Real-Valued Functions and Their Graphs] On which sets is the absolute value function A(x)=∣x∣A(x) = |x|A(x)=∣x∣ increasing, and on which decreasing?
Decreasing on the real numbers less than 0, increasing on the real numbers greater than 0. For x<0x < 0x<0 the graph is the line y=−xy = -xy=−x (slope −1-1−1 ); for x≥0x \ge 0x≥0 it is the line y=xy = xy=x (slope 1).Example: −3<−1-3 < -1−3<−1 and ∣−3∣=3>1=∣−1∣|-3| = 3 > 1 = |-1|∣−3∣=3>1=∣−1∣ ; 1<31 < 31<3 and ∣1∣=1<3=∣3∣|1| = 1 < 3 = |3|∣1∣=1<3=∣3∣ .
[Real-Valued Functions and Their Graphs] Let fff be a real-valued function whose domain contains a set SSS of real numbers. When is fff increasing on SSS , and when is fff an increasing function?
Increasing on SSS : for all x1,x2x_1, x_2x1,x2 in SSS , if x1<x2x_1 < x_2x1<x2 then f(x1)<f(x2)f(x_1) < f(x_2)f(x1)<f(x2) . Increasing function: increasing on its entire domain. (a) increasing, (b) decreasing: the height of the graph goes up, or down, from left to right.Example: f(x)=x3f(x) = x^3f(x)=x3 is an increasing function.
[Real-Valued Functions and Their Graphs] Let fff be a real-valued function whose domain contains a set SSS of real numbers. When is fff decreasing on SSS ?
For all x1,x2x_1, x_2x1,x2 in SSS , if x1<x2x_1 < x_2x1<x2 then f(x1)>f(x2)f(x_1) > f(x_2)f(x1)>f(x2) . fff is a decreasing function if it is decreasing on its entire domain.Example: g(x)=−xg(x) = -xg(x)=−x is decreasing on R\mathbb{R}R : x1<x2x_1 < x_2x1<x2 gives −x1>−x2-x_1 > -x_2−x1>−x2 .
[Real-Valued Functions and Their Graphs] How do you prove that a function f:R→Rf: \mathbb{R} \to \mathbb{R}f:R→R is increasing?
Suppose x1x_1x1 and x2x_2x2 are any real numbers with x1<x2x_1 < x_2x1<x2 , and show that f(x1)<f(x2)f(x_1) < f(x_2)f(x1)<f(x2) . To prove fff decreasing, show f(x1)>f(x2)f(x_1) > f(x_2)f(x1)>f(x2) instead.Example: f(x)=2x−3f(x) = 2x - 3f(x)=2x−3 : from x1<x2x_1 < x_2x1<x2 follows 2x1<2x22x_1 < 2x_22x1<2x2 , so 2x1−3<2x2−32x_1 - 3 < 2x_2 - 32x1−3<2x2−3 .
[Real-Valued Functions and Their Graphs] Why is every increasing function one-to-one?
If x1≠x2x_1 \ne x_2x1=x2 , say x1<x2x_1 < x_2x1<x2 , then f(x1)<f(x2)f(x_1) < f(x_2)f(x1)<f(x2) , so f(x1)≠f(x2)f(x_1) \ne f(x_2)f(x1)=f(x2) . The same argument shows that every decreasing function is one-to-one.Example: f(x)=x3f(x) = x^3f(x)=x3 is increasing, so no two real numbers have the same cube.
[Real-Valued Functions and Their Graphs] fff is increasing on a set SSS and MMM is a positive real number. Why is MfMfMf increasing on SSS ?
For x1<x2x_1 < x_2x1<x2 in SSS : f(x1)<f(x2)f(x_1) < f(x_2)f(x1)<f(x2) , and multiplying by the positive MMM keeps the direction of the inequality, so (Mf)(x1)<(Mf)(x2)(Mf)(x_1) < (Mf)(x_2)(Mf)(x1)<(Mf)(x2) . Example: f(x)=xf(x) = xf(x)=x and M=3M = 3M=3 : x1<x2x_1 < x_2x1<x2 gives 3x1<3x23x_1 < 3x_23x1<3x2 .
[Real-Valued Functions and Their Graphs] MMM is a nonzero real number and fff is increasing or decreasing on a set SSS . When is MfMfMf increasing on SSS , and when decreasing?
Positive multiple of an increasing function is increasing. Example: xxx is increasing, so 3x3x3x is increasing. Positive multiple of a decreasing function is decreasing. Example: −x-x−x is decreasing, so −3x-3x−3x is decreasing. Negative multiple of an increasing function is decreasing. Example: xxx is increasing, so −2x-2x−2x is decreasing. Negative multiple of a decreasing function is increasing. Example: −x-x−x is decreasing, so (−2)(−x)=2x(-2)(-x) = 2x(−2)(−x)=2x is increasing. Multiplying…
[O-, Ω-, and Θ-Notations] What are the O-, Ω- and Θ-notations used for?
To compare large-scale differences in the efficiency of algorithms, ignoring constant factors and differences that occur only for small inputs. They approximate a function by a simpler one for large values of the variable.Example: 17x6−45x3+2x+817x^6 - 45x^3 + 2x + 817x6−45x3+2x+8 is Θ(x6)\Theta(x^6)Θ(x6) .
[O-, Ω-, and Θ-Notations] Who introduced the O-notation, and who the Ω- and Θ-notations?
O: Paul Bachmann, 1894, in a book on analytic number theory. Ω and Θ: Donald Knuth. Read "big-O", "big-Omega", "big-Theta". Knuth started writing the multivolume "The Art of Computer Programming", a rigorous foundation of the analysis of algorithms, in the early 1960s.
[O-, Ω-, and Θ-Notations] Informally, for real-valued functions fff and ggg of a real variable xxx , what do " f(x)f(x)f(x) is O(g(x))O(g(x))O(g(x)) ", " f(x)f(x)f(x) is Ω(g(x))\Omega(g(x))Ω(g(x)) " and " f(x)f(x)f(x) is Θ(g(x))\Theta(g(x))Θ(g(x)) " mean?
f(x)f(x)f(x) is O(g(x))O(g(x))O(g(x)) : fff is of order at most ggg For sufficiently large xxx , the values of ∣f∣|f|∣f∣ are less than those of a multiple of ∣g∣|g|∣g∣ . Example: xxx is O(x2)O(x^2)O(x2) . f(x)f(x)f(x) is Ω(g(x))\Omega(g(x))Ω(g(x)) : fff is of order at least ggg For sufficiently large xxx , the values of ∣f∣|f|∣f∣ are greater than those of a multiple of ∣g∣|g|∣g∣ . Example: x2x^2x2 is Ω(x)\Omega(x)Ω(x) . f(x)f(x)f(x) is Θ(g(x))\Theta(g(x))Θ(g(x)) : fff is of order ggg For suffic…
[O-, Ω-, and Θ-Notations] fff and ggg are real-valued functions defined on the same set of nonnegative real numbers.Formally, when is fff of order at least ggg , written " f(x)f(x)f(x) is Ω(g(x))\Omega(g(x))Ω(g(x)) "?
When there exist a positive real number AAA and a nonnegative real number aaa such that A∣g(x)∣≤∣f(x)∣A|g(x)| \le |f(x)|A∣g(x)∣≤∣f(x)∣ for all real numbers x>ax > ax>a . Example: 2∣x4∣≤∣2x4+3x3+5∣2|x^4| \le |2x^4 + 3x^3 + 5|2∣x4∣≤∣2x4+3x3+5∣ for all x>0x > 0x>0 , so 2x4+3x3+52x^4 + 3x^3 + 52x4+3x3+5 is Ω(x4)\Omega(x^4)Ω(x4) (with A=2A = 2A=2 , a=0a = 0a=0 ).
[O-, Ω-, and Θ-Notations] fff and ggg are real-valued functions defined on the same set of nonnegative real numbers.Formally, when is fff of order at most ggg , written " f(x)f(x)f(x) is O(g(x))O(g(x))O(g(x)) "?
When there exist a positive real number BBB and a nonnegative real number bbb such that ∣f(x)∣≤B∣g(x)∣|f(x)| \le B|g(x)|∣f(x)∣≤B∣g(x)∣ for all real numbers x>bx > bx>b . Example: ∣2x4+3x3+5∣≤10∣x4∣|2x^4 + 3x^3 + 5| \le 10|x^4|∣2x4+3x3+5∣≤10∣x4∣ for all x>1x > 1x>1 , so 2x4+3x3+52x^4 + 3x^3 + 52x4+3x3+5 is O(x4)O(x^4)O(x4) (with B=10B = 10B=10 , b=1b = 1b=1 ).
[O-, Ω-, and Θ-Notations] fff and ggg are real-valued functions defined on the same set of nonnegative real numbers.Formally, when is fff of order ggg , written " f(x)f(x)f(x) is Θ(g(x))\Theta(g(x))Θ(g(x)) "?
When there exist positive real numbers AAA , BBB and a nonnegative real number kkk such that A∣g(x)∣≤∣f(x)∣≤B∣g(x)∣A|g(x)| \le |f(x)| \le B|g(x)|A∣g(x)∣≤∣f(x)∣≤B∣g(x)∣ for all real numbers x>kx > kx>k . Example: 2∣x4∣≤∣2x4+3x3+5∣≤10∣x4∣2|x^4| \le |2x^4 + 3x^3 + 5| \le 10|x^4|2∣x4∣≤∣2x4+3x3+5∣≤10∣x4∣ for all x>1x > 1x>1 , so 2x4+3x3+52x^4 + 3x^3 + 52x4+3x3+5 is Θ(x4)\Theta(x^4)Θ(x4) .
[O-, Ω-, and Θ-Notations] Express in Θ-notation: 10∣x6∣≤∣17x6−45x3+2x+8∣≤30∣x6∣10|x^6| \le |17x^6 - 45x^3 + 2x + 8| \le 30|x^6|10∣x6∣≤∣17x6−45x3+2x+8∣≤30∣x6∣ for all real numbers x>2x > 2x>2 .
17x6−45x3+2x+817x^6 - 45x^3 + 2x + 817x6−45x3+2x+8 is Θ(x6)\Theta(x^6)Θ(x6) . Take A=10A = 10A=10 , B=30B = 30B=30 and k=2k = 2k=2 in the definition of Θ-notation.
[O-, Ω-, and Θ-Notations] In the statement " 3x+43\sqrt{x} + 43x+4 is Θ(x1/2)\Theta(x^{1/2})Θ(x1/2) ", what do the expressions 3x+43\sqrt{x} + 43x+4 and x1/2x^{1/2}x1/2 stand for?
The functions fff and ggg defined by f(x)=3x+4f(x) = 3\sqrt{x} + 4f(x)=3x+4 and g(x)=x1/2g(x) = x^{1/2}g(x)=x1/2 , not their values at one xxx . Their common domain is usually the largest set of nonnegative real numbers on which both formulas are defined. This traditional use breaks the usual distinction between a function fff and its value f(x)f(x)f(x) .
[O-, Ω-, and Θ-Notations] A∣g(x)∣≤∣f(x)∣A|g(x)| \le |f(x)|A∣g(x)∣≤∣f(x)∣ for all real x>ax > ax>a , and ∣f(x)∣≤B∣g(x)∣|f(x)| \le B|g(x)|∣f(x)∣≤B∣g(x)∣ for all real x>bx > bx>b .Which kkk shows that f(x)f(x)f(x) is Θ(g(x))\Theta(g(x))Θ(g(x)) ?
kkk = the larger of aaa and bbb . For x>kx > kx>k both inequalities hold, so A∣g(x)∣≤∣f(x)∣≤B∣g(x)∣A|g(x)| \le |f(x)| \le B|g(x)|A∣g(x)∣≤∣f(x)∣≤B∣g(x)∣ .Example: 15∣x∣≤∣15x(2x+9)x+1∣15|\sqrt{x}| \le \left|\frac{15\sqrt{x}(2x + 9)}{x + 1}\right|15∣x∣≤∣∣x+115x(2x+9)∣∣ for x>0x > 0x>0 , and ∣15x(2x+9)x+1∣≤45∣x∣\left|\frac{15\sqrt{x}(2x + 9)}{x + 1}\right| \le 45|\sqrt{x}|∣∣x+115x(2x+9)∣∣≤45∣x∣ for x>7x > 7x>7 ; so with k=7k = 7k=7 the function is Θ(x)\Theta(\sqrt{x})Θ(x) .
[O-, Ω-, and Θ-Notations] What are the three basic properties of the O-, Ω- and Θ-notations, for real-valued functions fff , ggg , hhh defined on the same set of nonnegative real numbers?
Θ means both Ω and O f(x)f(x)f(x) is Ω(g(x))\Omega(g(x))Ω(g(x)) and f(x)f(x)f(x) is O(g(x))O(g(x))O(g(x)) if, and only if, f(x)f(x)f(x) is Θ(g(x))\Theta(g(x))Θ(g(x)) . Example: 2x4+3x3+52x^4 + 3x^3 + 52x4+3x3+5 is Ω(x4)\Omega(x^4)Ω(x4) and O(x4)O(x^4)O(x4) , so it is Θ(x4)\Theta(x^4)Θ(x4) . Ω and O are converse f(x)f(x)f(x) is Ω(g(x))\Omega(g(x))Ω(g(x)) if, and only if, g(x)g(x)g(x) is O(f(x))O(f(x))O(f(x)) . Example: x2x^2x2 is Ω(x)\Omega(x)Ω(x) , and xxx is O(x2)O(x^2)O(x2) . Transitivity of…
[O-, Ω-, and Θ-Notations] f(x)f(x)f(x) is Ω(g(x))\Omega(g(x))Ω(g(x)) : there are A>0A > 0A>0 and a≥0a \ge 0a≥0 with A∣g(x)∣≤∣f(x)∣A|g(x)| \le |f(x)|A∣g(x)∣≤∣f(x)∣ for all real x>ax > ax>a .Why does it follow that g(x)g(x)g(x) is O(f(x))O(f(x))O(f(x)) ?
Dividing by AAA gives ∣g(x)∣≤1A∣f(x)∣|g(x)| \le \frac1A |f(x)|∣g(x)∣≤A1∣f(x)∣ for all x>ax > ax>a , so B=1AB = \frac1AB=A1 and b=ab = ab=a work in the definition of O. Example: 2∣x4∣≤∣2x4+3x3+5∣2|x^4| \le |2x^4 + 3x^3 + 5|2∣x4∣≤∣2x4+3x3+5∣ for x>0x > 0x>0 gives ∣x4∣≤12∣2x4+3x3+5∣|x^4| \le \frac12 |2x^4 + 3x^3 + 5|∣x4∣≤21∣2x4+3x3+5∣ , so x4x^4x4 is O(2x4+3x3+5)O(2x^4 + 3x^3 + 5)O(2x4+3x3+5) .
[O-, Ω-, and Θ-Notations] ∣f(x)∣≤B1∣g(x)∣|f(x)| \le B_1|g(x)|∣f(x)∣≤B1∣g(x)∣ for all real x>b1x > b_1x>b1 , and ∣g(x)∣≤B2∣h(x)∣|g(x)| \le B_2|h(x)|∣g(x)∣≤B2∣h(x)∣ for all real x>b2x > b_2x>b2 .How does the proof show that f(x)f(x)f(x) is O(h(x))O(h(x))O(h(x)) ?
For x>bx > bx>b = the greater of b1,b2b_1, b_2b1,b2 : ∣f(x)∣≤B1∣g(x)∣≤B1B2∣h(x)∣|f(x)| \le B_1|g(x)| \le B_1B_2|h(x)|∣f(x)∣≤B1∣g(x)∣≤B1B2∣h(x)∣ , so B=B1B2B = B_1B_2B=B1B2 and this bbb work. Example: ∣x∣≤1⋅∣x2∣|x| \le 1 \cdot |x^2|∣x∣≤1⋅∣x2∣ for x>1x > 1x>1 and ∣x2∣≤1⋅∣x3∣|x^2| \le 1 \cdot |x^3|∣x2∣≤1⋅∣x3∣ for x>1x > 1x>1 give ∣x∣≤1⋅∣x3∣|x| \le 1 \cdot |x^3|∣x∣≤1⋅∣x3∣ for x>1x > 1x>1 .
[O-, Ω-, and Θ-Notations] rrr and sss are rational numbers with r<sr < sr<s , and x>1x > 1x>1 . How do xrx^rxr and xsx^sxs compare?
xr<xs\boldsymbol{x^r < x^s}xr<xs Simplest case: from 1<x1 < x1<x , multiplying by the positive xxx gives x<x2x < x^2x<x2 , and again x2<x3x^2 < x^3x2<x3 , so 1<x<x2<x31 < x < x^2 < x^31<x<x2<x3 .Example: x=4x = 4x=4 : 41/2=2<43/2=84^{1/2} = 2 < 4^{3/2} = 841/2=2<43/2=8 .
[O-, Ω-, and Θ-Notations] rrr and sss are rational numbers with r<sr < sr<s . What is the relation between xrx^rxr and xsx^sxs in O-notation?
xrx^rxr is O(xs)O(x^s)O(xs) . Because ∣xr∣<1⋅∣xs∣|x^r| < 1 \cdot |x^s|∣xr∣<1⋅∣xs∣ for all real x>1x > 1x>1 . For x>1x > 1x>1 , the graph of y=xry = x^ry=xr lies below the graph of y=xsy = x^sy=xs when r<sr < sr<s .Example: x1/2x^{1/2}x1/2 is O(x)O(x)O(x) and x2x^2x2 is O(x3)O(x^3)O(x3) .
[O-, Ω-, and Θ-Notations] How do you show that 3x3+2x+7≤12x33x^3 + 2x + 7 \le 12x^33x3+2x+7≤12x3 for every real number x>1x > 1x>1 ?
Replace each lower power of xxx by x3x^3x3 , which is larger when x>1x > 1x>1 . x<x3x < x^3x<x3 and 1<x31 < x^31<x3 give 2x<2x32x < 2x^32x<2x3 and 7<7x37 < 7x^37<7x3 . Adding 3x3≤3x33x^3 \le 3x^33x3≤3x3 : 3x3+2x+7≤3x3+2x3+7x3=12x33x^3 + 2x + 7 \le 3x^3 + 2x^3 + 7x^3 = 12x^33x3+2x+7≤3x3+2x3+7x3=12x3 .
[O-, Ω-, and Θ-Notations] In a chain of inequalities, what does an arrow ⇒\Rightarrow⇒ at the beginning of a line mean?
Every number xxx that makes the inequality in the line before true also makes the inequality in this line true. Example: a line " x>1x > 1x>1 " followed by a line " ⇒ x2>x\Rightarrow \ x^2 > x⇒ x2>x " means that every xxx with x>1x > 1x>1 also has x2>xx^2 > xx2>x .
[O-, Ω-, and Θ-Notations] Use the definitions to show that 2x4+3x3+52x^4 + 3x^3 + 52x4+3x3+5 is Θ(x4)\Theta(x^4)Θ(x4) .
Ω with A=2A = 2A=2 , a=0a = 0a=0 ; O with B=10B = 10B=10 , b=1b = 1b=1 ; both together give Θ. For x>0x > 0x>0 : 2x4≤2x4+3x3+52x^4 \le 2x^4 + 3x^3 + 52x4≤2x4+3x3+5 because 3x3+5>03x^3 + 5 > 03x3+5>0 .For x>1x > 1x>1 : 2x4+3x3+5≤2x4+3x4+5x4=10x42x^4 + 3x^3 + 5 \le 2x^4 + 3x^4 + 5x^4 = 10x^42x4+3x3+5≤2x4+3x4+5x4=10x4 , because x3<x4x^3 < x^4x3<x4 and 1<x41 < x^41<x4 .All terms are positive, so the absolute value signs change nothing.
[O-, Ω-, and Θ-Notations] What do the triangle inequality and its version for differences say?
∣a+b∣≤∣a∣+∣b∣\boldsymbol{|a + b| \le |a| + |b|}∣a+b∣≤∣a∣+∣b∣ and ∣a−b∣≤∣a∣+∣b∣\boldsymbol{|a - b| \le |a| + |b|}∣a−b∣≤∣a∣+∣b∣ for all real numbers aaa and bbb . The second follows from the first with −b-b−b in place of bbb : ∣a+(−b)∣≤∣a∣+∣−b∣=∣a∣+∣b∣|a + (-b)| \le |a| + |-b| = |a| + |b|∣a+(−b)∣≤∣a∣+∣−b∣=∣a∣+∣b∣ .Example: a=3a = 3a=3 , b=−5b = -5b=−5 : ∣3−(−5)∣=8≤3+5|3 - (-5)| = 8 \le 3 + 5∣3−(−5)∣=8≤3+5 .
[O-, Ω-, and Θ-Notations] How does one show that 3x3−1000x−2003x^3 - 1000x - 2003x3−1000x−200 is O(x3)O(x^3)O(x3) ?
For x>1x > 1x>1 : ∣3x3−1000x−200∣≤3x3+1000x+200≤1203x3|3x^3 - 1000x - 200| \le 3x^3 + 1000x + 200 \le 1203x^3∣3x3−1000x−200∣≤3x3+1000x+200≤1203x3 , so B=1203B = 1203B=1203 and b=1b = 1b=1 work. First step: triangle inequality ( x>1x > 1x>1 makes all terms positive). Second step: x<x3x < x^3x<x3 and 1<x31 < x^31<x3 for x>1x > 1x>1 .
[O-, Ω-, and Θ-Notations] ∣3x3−1000x−200∣≤1203∣x3∣|3x^3 - 1000x - 200| \le 1203|x^3|∣3x3−1000x−200∣≤1203∣x3∣ for all real x>1x > 1x>1 .Why is 3x3−1000x−2003x^3 - 1000x - 2003x3−1000x−200 also O(xs)O(x^s)O(xs) for every integer s>3s > 3s>3 ?
For x>1x > 1x>1 , x3<xsx^3 < x^sx3<xs , so ∣3x3−1000x−200∣≤1203∣x3∣≤1203∣xs∣|3x^3 - 1000x - 200| \le 1203|x^3| \le 1203|x^s|∣3x3−1000x−200∣≤1203∣x3∣≤1203∣xs∣ . Example: 3x3−1000x−2003x^3 - 1000x - 2003x3−1000x−200 is O(x4)O(x^4)O(x4) with B=1203B = 1203B=1203 , b=1b = 1b=1 .
[O-, Ω-, and Θ-Notations] To show with the definition that a polynomial anxn+⋯+a1x+a0a_nx^n + \dots + a_1x + a_0anxn+⋯+a1x+a0 ( an≠0a_n \ne 0an=0 ) is Ω(xn)\Omega(x^n)Ω(xn) , how does the book choose the numbers aaa and AAA ?
a=2⋅∣a0∣+∣a1∣+⋯+∣an−1∣∣an∣\boldsymbol{a = 2 \cdot \frac{|a_0| + |a_1| + \dots + |a_{n-1}|}{|a_n|}}a=2⋅∣an∣∣a0∣+∣a1∣+⋯+∣an−1∣ (or 1, if that is larger) and A=12∣an∣\boldsymbol{A = \frac12 |a_n|}A=21∣an∣ Then A∣xn∣≤∣anxn+⋯+a1x+a0∣A|x^n| \le |a_nx^n + \dots + a_1x + a_0|A∣xn∣≤∣anxn+⋯+a1x+a0∣ for all x>ax > ax>a .Example: 3x3−1000x−2003x^3 - 1000x - 2003x3−1000x−200 : a=2(1000+200)3=800a = \frac{2(1000 + 200)}{3} = 800a=32(1000+200)=800 and A=32A = \frac32A=23 .
[O-, Ω-, and Θ-Notations] Why is ∣3x3−1000x−200∣>32∣x3∣|3x^3 - 1000x - 200| > \frac32 |x^3|∣3x3−1000x−200∣>23∣x3∣ for all x>800x > 800x>800 ?
For x>800x > 800x>800 : 32x3>1000x+200\frac32 x^3 > 1000x + 20023x3>1000x+200 , so 3x3−1000x−200>3x3−32x3=32x33x^3 - 1000x - 200 > 3x^3 - \frac32 x^3 = \frac32 x^33x3−1000x−200>3x3−23x3=23x3 . x>800=2⋅10003+2⋅2003>2⋅10003⋅1x+2⋅2003⋅1x2x > 800 = \frac{2 \cdot 1000}{3} + \frac{2 \cdot 200}{3} > \frac{2 \cdot 1000}{3} \cdot \frac1x + \frac{2 \cdot 200}{3} \cdot \frac1{x^2}x>800=32⋅1000+32⋅200>32⋅1000⋅x1+32⋅200⋅x21 , since 1x<1\frac1x < 1x1<1 and 1x2<1\frac1{x^2} < 1x21<1 . Multiplying b…
[O-, Ω-, and Θ-Notations] 32∣x3∣≤∣3x3−1000x−200∣\frac32 |x^3| \le |3x^3 - 1000x - 200|23∣x3∣≤∣3x3−1000x−200∣ for all real x>800x > 800x>800 .Why is 3x3−1000x−2003x^3 - 1000x - 2003x3−1000x−200 also Ω(xr)\Omega(x^r)Ω(xr) for every integer r<3r < 3r<3 ?
For x>800>1x > 800 > 1x>800>1 , xr<x3x^r < x^3xr<x3 , so 32∣xr∣<32∣x3∣≤∣3x3−1000x−200∣\frac32|x^r| < \frac32|x^3| \le |3x^3 - 1000x - 200|23∣xr∣<23∣x3∣≤∣3x3−1000x−200∣ . Example: 3x3−1000x−2003x^3 - 1000x - 2003x3−1000x−200 is Ω(x2)\Omega(x^2)Ω(x2) and Ω(x)\Omega(x)Ω(x) .
[O-, Ω-, and Θ-Notations] Theorem on polynomial orders. Let a0,a1,…,ana_0, a_1, \dots, a_na0,a1,…,an be real numbers with an≠0a_n \ne 0an=0 . What orders does anxn+an−1xn−1+⋯+a1x+a0a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0anxn+an−1xn−1+⋯+a1x+a0 have?
O O(xs)O(x^s)O(xs) for all integers s≥ns \ge ns≥n . Example: 3x3−1000x−2003x^3 - 1000x - 2003x3−1000x−200 is O(x3)O(x^3)O(x3) and O(x4)O(x^4)O(x4) . Ω Ω(xr)\Omega(x^r)Ω(xr) for all integers r≤nr \le nr≤n . Example: 3x3−1000x−2003x^3 - 1000x - 2003x3−1000x−200 is Ω(x3)\Omega(x^3)Ω(x3) and Ω(x)\Omega(x)Ω(x) . Θ Θ(xn)\Theta(x^n)Θ(xn) . Example: 3x3−1000x−2003x^3 - 1000x - 2003x3−1000x−200 is Θ(x3)\Theta(x^3)Θ(x3) . It can be proved with calculus, or without calculus as in the examples with explici…
[O-, Ω-, and Θ-Notations] By the theorem on polynomial orders, a polynomial p(x)p(x)p(x) is Θ(xn)\Theta(x^n)Θ(xn) , where nnn is the degree of p(x)p(x)p(x) .
Example: 7x5+5x3−x+47x^5 + 5x^3 - x + 47x5+5x3−x+4 has degree 5, so it is Θ(x5)\Theta(x^5)Θ(x5) .
[O-, Ω-, and Θ-Notations] Find orders among the power functions for f(x)=7x5+5x3−x+4f(x) = 7x^5 + 5x^3 - x + 4f(x)=7x5+5x3−x+4 and g(x)=(x−1)(x+1)4g(x) = \frac{(x - 1)(x + 1)}{4}g(x)=4(x−1)(x+1) .
f(x)f(x)f(x) is Θ(x5)\Theta(x^5)Θ(x5) , and g(x)g(x)g(x) is Θ(x2)\Theta(x^2)Θ(x2) . g(x)=14(x2−1)=14x2−14g(x) = \frac14(x^2 - 1) = \frac14 x^2 - \frac14g(x)=41(x2−1)=41x2−41 , a polynomial of degree 2.
[O-, Ω-, and Θ-Notations] Why is x2x^2x2 not O(x)O(x)O(x) ?
If ∣x2∣≤B∣x∣|x^2| \le B|x|∣x2∣≤B∣x∣ for all x>bx > bx>b , take an xxx greater than both BBB and bbb : then x⋅x>B⋅xx \cdot x > B \cdot xx⋅x>B⋅x , i.e. ∣x2∣>B∣x∣|x^2| > B|x|∣x2∣>B∣x∣ , a contradiction. So x2x^2x2 is not Θ(x)\Theta(x)Θ(x) either, because Θ implies O.
[O-, Ω-, and Θ-Notations] Let nnn be a positive integer, a0,…,ana_0, \dots, a_na0,…,an real numbers with an≠0a_n \ne 0an=0 , and mmm an integer with m<nm < nm<n . Is anxn+⋯+a1x+a0a_nx^n + \dots + a_1x + a_0anxn+⋯+a1x+a0 O(xm)O(x^m)O(xm) ? Is it Θ(xm)\Theta(x^m)Θ(xm) ?
Neither: it is not O(xm)O(x^m)O(xm) and not Θ(xm)\Theta(x^m)Θ(xm) . Example: x5+1x^5 + 1x5+1 is not O(x2)O(x^2)O(x2) .
[O-, Ω-, and Θ-Notations] Why are the power functions x0,x1,x2,…x^0, x^1, x^2, \dotsx0,x1,x2,… convenient benchmarks for the orders of polynomial functions?
Every polynomial function has the same order as one of them, and no two of them have the same order. Example: 14x2−14\frac14 x^2 - \frac1441x2−41 is Θ(x2)\Theta(x^2)Θ(x2) , and x2x^2x2 is not Θ(x3)\Theta(x^3)Θ(x3) .
[O-, Ω-, and Θ-Notations] f(x)f(x)f(x) is Θ(g(x))\Theta(g(x))Θ(g(x)) for functions fff , ggg of a real variable xxx . Why is f(n)f(n)f(n) then also Θ(g(n))\Theta(g(n))Θ(g(n)) for the integer variable nnn ?
A∣g(x)∣≤∣f(x)∣≤B∣g(x)∣A|g(x)| \le |f(x)| \le B|g(x)|A∣g(x)∣≤∣f(x)∣≤B∣g(x)∣ holds for all real x>kx > kx>k , so in particular for all integers n>kn > kn>k . By tradition, xxx denotes a real variable and nnn an integer variable.Example: 12x2+12x\frac12 x^2 + \frac12 x21x2+21x is Θ(x2)\Theta(x^2)Θ(x2) , so 12n2+12n\frac12 n^2 + \frac12 n21n2+21n is Θ(n2)\Theta(n^2)Θ(n2) .
[O-, Ω-, and Θ-Notations] For a positive integer variable nnn , find an order for 1+2+3+⋯+n1 + 2 + 3 + \dots + n1+2+3+⋯+n .
Θ(n2)\boldsymbol{\Theta(n^2)}Θ(n2) 1+2+⋯+n=n(n+1)2=12n2+12n1 + 2 + \dots + n = \frac{n(n + 1)}{2} = \frac12 n^2 + \frac12 n1+2+⋯+n=2n(n+1)=21n2+21n , a polynomial of degree 2.
[O-, Ω-, and Θ-Notations] f(x)f(x)f(x) is a quotient of two sums of terms axrax^raxr ( aaa real, rrr nonnegative rational, nonzero coefficients for the largest exponents). What is the degree ddd of fff , and what are its orders?
ddd = largest exponent of the numerator minus largest exponent of the denominator; f(x)f(x)f(x) is Θ(xd)\Theta(x^d)Θ(xd) , is O(xc)O(x^c)O(xc) for all real c>dc > dc>d , and is not O(xc)O(x^c)O(xc) for any real c<dc < dc<d . Example: x3/2+1x+1\frac{x^{3/2} + 1}{x + 1}x+1x3/2+1 has d=32−1=12d = \frac32 - 1 = \frac12d=23−1=21 , so it is Θ(x1/2)\Theta(x^{1/2})Θ(x1/2) .
[O-, Ω-, and Θ-Notations] Find an order for (x3/2+3)(x−2)2x1/2(2x1/2+1)\displaystyle\frac{(x^{3/2} + 3)(x - 2)^2}{x^{1/2}(2x^{1/2} + 1)}x1/2(2x1/2+1)(x3/2+3)(x−2)2 among the rational power functions.
Θ(x5/2)\boldsymbol{\Theta(x^{5/2})}Θ(x5/2) The numerator expands to x7/2−4x5/2+4x3/2+3x2−12x+12x^{7/2} - 4x^{5/2} + 4x^{3/2} + 3x^2 - 12x + 12x7/2−4x5/2+4x3/2+3x2−12x+12 (largest exponent 72\frac7227 ), the denominator to 2x+x1/22x + x^{1/2}2x+x1/2 (largest exponent 1): d=72−1=52d = \frac72 - 1 = \frac52d=27−1=25 .It is also O(xc)O(x^c)O(xc) for every c>52c > \frac52c>25 and not O(xc)O(x^c)O(xc) for any c<52c < \frac52c<25 .
[Algorithm Efficiency I] Who may have been the first to suggest a concrete way to measure the amount of work of a computation, and what was it?
Alan Turing, 1948: count the operations, such as additions, subtractions, multiplications, divisions and recordings of numbers. In 1864, Charles Babbage (1792–1871), designer of the Analytical Engine, already asked by which course of calculation a machine reaches a result in the shortest time.
[Algorithm Efficiency I] What does the sequential search algorithm do to find an item xxx in an array a[1],a[2],…,a[n]a[1], a[2], \dots, a[n]a[1],a[2],…,a[n] ?
It compares xxx with a[1]a[1]a[1] , then with a[2]a[2]a[2] , and so on, and stops at the first match; if no item matches, xxx is not in the array. Example: searching a[1],…,a[7]a[1], \dots, a[7]a[1],…,a[7] for x=a[5]x = a[5]x=a[5] takes five comparisons.
[Algorithm Efficiency I] What two aspects of the efficiency of an algorithm are important?
The time needed to execute it, and the memory space needed when it runs. One algorithm can use time more efficiently but memory less efficiently than another, which forces a trade-off based on the available resources.
[Algorithm Efficiency I] On which two properties of the input does the execution time of an algorithm depend?
The size nnn of the input, and the nature of the input data. So time is expressed as a function of nnn , and analyzed for the best case, the worst case and the average case.Example: sequential search in a list of length nnn takes 1 step if the item is first, and nnn steps if it is last.
[Algorithm Efficiency I] Which operations does the book count as elementary operations?
Addition, subtraction, multiplication, division, and comparisons written explicitly in an if-statement with <<< , ≤\le≤ , >>> , ≥\ge≥ , === or ≠\ne= . Which operations matter depends on the problem: additions and multiplications for evaluating a polynomial, comparisons for searching a list.
[Algorithm Efficiency I] Why is the execution time of an algorithm approximately proportional to the number of elementary operations it performs?
Each elementary operation takes no longer than the slowest one. Differences between operations and between machines are ignored when rough estimates suffice to show that one algorithm is clearly better.
[Algorithm Efficiency I] For an input of size nnn , algorithm A needs between 10n10n10n and 20n20n20n elementary operations, algorithm B between 2n22n^22n2 and 4n24n^24n2 (for large nnn ). For which nnn is the maximum for A less than the minimum for B?
For all n>10n > 10n>10 , because 20n<2n220n < 2n^220n<2n2 exactly when n>10n > 10n>10 . A has worst-case order nnn , B has worst-case order n2n^2n2 .Example: n=1000n = 1000n=1000 : 20n=20,00020n = 20{,}00020n=20,000 , but 2n2=2,000,0002n^2 = 2{,}000{,}0002n2=2,000,000 .
[Algorithm Efficiency I] For every input of size nnn , algorithm AAA performs f(n)f(n)f(n) elementary operations (a number depending on nnn alone). When is AAA of order g(n)g(n)g(n) , written AAA is Θ(g(n))\Theta(g(n))Θ(g(n)) ?
When f(n)f(n)f(n) is Θ(g(n))\Theta(g(n))Θ(g(n)) . Example: an algorithm segment with 2n−22n - 22n−2 additions and multiplications is Θ(n)\Theta(n)Θ(n) .
[Algorithm Efficiency I] The number of elementary operations of algorithm AAA depends on the input data as well as on the input size nnn . What are the best-case order and the worst-case order of AAA ?
Best-case order g(n)g(n)g(n) such that b(n)b(n)b(n) is Θ(g(n))\Theta(g(n))Θ(g(n)) , where b(n)b(n)b(n) is the minimum number of elementary operations of AAA over all inputs of size nnn . Example: sequential search has b(n)=1b(n) = 1b(n)=1 , so it is Θ(1)\Theta(1)Θ(1) in the best case. Worst-case order g(n)g(n)g(n) such that w(n)w(n)w(n) is Θ(g(n))\Theta(g(n))Θ(g(n)) , where w(n)w(n)w(n) is the maximum number of elementary operations of AAA over all inputs of size nnn . Example: sequential searc…
[Algorithm Efficiency I] What are the best-case and the worst-case orders of sequential search in an array a[1],…,a[n]a[1], \dots, a[n]a[1],…,a[n] , and when do these cases occur?
Best case Θ(1)\Theta(1)Θ(1) : x=a[1]x = a[1]x=a[1] , one comparison. Worst case Θ(n)\Theta(n)Θ(n) : x=a[n]x = a[n]x=a[n] or xxx not in the array, nnn comparisons. Θ(1)=Θ(n0)\Theta(1) = \Theta(n^0)Θ(1)=Θ(n0) .
[Algorithm Efficiency I] At one operation per nanosecond ( 10−910^{-9}10−9 s), about how long do n2n^2n2 , n3n^3n3 and 2n2^n2n operations take for n=100,000n = 100{,}000n=100,000 ?
n2n^2n2 : 10 seconds; n3n^3n3 : 11.6 days; 2n2^n2n : about 3.1×10300863.1 \times 10^{30086}3.1×1030086 years. f(n)n=10n=1,000n=100,000n=107log2n3.3×10−9 s10−8 s1.7×10−8 s2.3×10−8 sn10−8 s10−6 s0.0001 s0.01 snlog2n3.3×10−8 s10−5 s0.0017 s0.23 sn210−7 s0.001 s10 s27.8 hoursn310−6 s1 s11.6 days31,688 yr2n10−6 s3.4×10284 yr3.1×1030086 yr2.9×103010283 yr\begin{array}{l|llll} f(n) & n = 10 & n = 1{,}000 & n = 100{,}000 & n = 10^7 \\ \hline \log_2 n & 3.3 \times 10^{-9}\text{ s} & 10^{-8}\text{ s} &…
[Algorithm Efficiency I] How many times is the loop "for i:=ai := ai:=a to bbb " iterated, for integers a≤ba \le ba≤b ?
b−a+1\boldsymbol{b - a + 1}b−a+1 times (top index minus bottom index plus 1). Example: "for i:=2i := 2i:=2 to nnn " is iterated n−1n - 1n−1 times.
[Algorithm Efficiency I] nnn is a positive integer. How many additions and multiplications does this algorithm segment perform, and what is its order? p:=0, x:=2for i:=2 to np:=(p+i)⋅xnext i\begin{array}{l} p := 0, \ x := 2 \\ \textbf{for } i := 2 \textbf{ to } n \\ \quad p := (p + i) \cdot x \\ \textbf{next } i \end{array}p:=0, x:=2for i:=2 to np:=(p+i)⋅xnext i
2n−22n - 22n−2 , so the segment is Θ(n)\Theta(n)Θ(n) . One addition and one multiplication in each of the n−2+1=n−1n - 2 + 1 = n - 1n−2+1=n−1 iterations.Example: n=4n = 4n=4 : i=2,3,4i = 2, 3, 4i=2,3,4 , so 3 additions and 3 multiplications, 2⋅4−2=62 \cdot 4 - 2 = 62⋅4−2=6 .
[Algorithm Efficiency I] nnn is a positive integer. How many additions, subtractions and multiplications does this algorithm segment perform, and what is its order? s:=0for i:=1 to nfor j:=1 to is:=s+j⋅(i−j+1)next jnext i\begin{array}{l} s := 0 \\ \textbf{for } i := 1 \textbf{ to } n \\ \quad \textbf{for } j := 1 \textbf{ to } i \\ \quad \quad s := s + j \cdot (i - j + 1) \\ \quad \textbf{next } j \\ \textbf{next } i \end{array}s:=0for i:=1 to nfor j:=1 to is:=s+j⋅(i−j+1)next jnext i
4⋅n(n+1)2=2n(n+1)4 \cdot \frac{n(n + 1)}{2} = 2n(n + 1)4⋅2n(n+1)=2n(n+1) , so the segment is Θ(n2)\Theta(n^2)Θ(n2) . Each inner iteration has 2 additions, 1 subtraction and 1 multiplication. The inner loop runs iii times for each iii : 1+2+⋯+n=n(n+1)21 + 2 + \dots + n = \frac{n(n + 1)}{2}1+2+⋯+n=2n(n+1) iterations.Example: n=3n = 3n=3 : 6 inner iterations, 24 operations, 2⋅3⋅4=242 \cdot 3 \cdot 4 = 242⋅3⋅4=24 .
[Algorithm Efficiency I] To count the iterations of nested for-next loops, you can make a table of the values of the loop variables. What does each column of the table represent?
One iteration of the innermost loop. Example: "for i:=1i := 1i:=1 to nnn , for j:=1j := 1j:=1 to iii ": i122333⋯nj112123⋯n\begin{array}{c|cccccccc} i & 1 & 2 & 2 & 3 & 3 & 3 & \cdots & n \\ j & 1 & 1 & 2 & 1 & 2 & 3 & \cdots & n \end{array}ij112122313233⋯⋯nn 1+2+⋯+n1 + 2 + \dots + n1+2+⋯+n columns in total.
[Algorithm Efficiency I] Why is the number of pairs (i,j)(i, j)(i,j) of integers with 1≤j≤i≤n1 \le j \le i \le n1≤j≤i≤n equal to (n+12)=n(n+1)2\binom{n + 1}{2} = \frac{n(n + 1)}{2}(2n+1)=2n(n+1) ?
Each pair is a way to place two ×'s in the nnn categories 1,2,…,n1, 2, \dots, n1,2,…,n (repetition allowed), and there are (n−1+22)=(n+12)\binom{n - 1 + 2}{2} = \binom{n + 1}{2}(2n−1+2)=(2n+1) such ways. This counts the iterations of "for i:=1i := 1i:=1 to nnn , for j:=1j := 1j:=1 to iii ". The method is simpler than summing when loops are nested more than twice.Example: n=3n = 3n=3 : (1,1),(2,1),(2,2),(3,1),(3,2),(3,3)(1,1), (2,1), (2,2), (3,1), (3,2), (3,3)(1,1),(2,1),(2,2),(3,1),(3,2),(3,3…
[Algorithm Efficiency I] nnn is a positive integer. How many subtractions does this algorithm segment perform, and what is its order? for i:=⌊n/2⌋ to na:=n−inext i\begin{array}{l} \textbf{for } i := \lfloor n/2 \rfloor \textbf{ to } n \\ \quad a := n - i \\ \textbf{next } i \end{array}for i:=⌊n/2⌋ to na:=n−inext i
n−⌊n/2⌋+1n - \lfloor n/2 \rfloor + 1n−⌊n/2⌋+1 : that is n+22\frac{n + 2}{2}2n+2 for even nnn and n+32\frac{n + 3}{2}2n+3 for odd nnn ; Θ(n)\Theta(n)Θ(n) in both cases. For odd nnn , ⌊n/2⌋=n−12\lfloor n/2 \rfloor = \frac{n - 1}{2}⌊n/2⌋=2n−1 , and n−n−12+1=n+32n - \frac{n - 1}{2} + 1 = \frac{n + 3}{2}n−2n−1+1=2n+3 .Example: n=5n = 5n=5 : i=2,3,4,5i = 2, 3, 4, 5i=2,3,4,5 , four subtractions, and 5+32=4\frac{5 + 3}{2} = 425+3=4 .
[Algorithm Efficiency I] What is the idea of insertion sort on an array a[1],a[2],…,a[n]a[1], a[2], \dots, a[n]a[1],a[2],…,a[n] ?
Lengthen the sorted initial part of the array step by step: step kkk inserts a[k]a[k]a[k] into its correct position relative to a[1],…,a[k−1]a[1], \dots, a[k - 1]a[1],…,a[k−1] . After step kkk , a[1],…,a[k]a[1], \dots, a[k]a[1],…,a[k] is in ascending order. When the last item has been placed, the entire array is in ascending order.Example: in 3,6,53, 6, 53,6,5 , inserting 5 gives 3,5,63, 5, 63,5,6 .
[Algorithm Efficiency I] In the step of insertion sort that places a[k]a[k]a[k] , how is a[k]a[k]a[k] moved into position among the sorted a[1],…,a[k−1]a[1], \dots, a[k - 1]a[1],…,a[k−1] ?
Save x:=a[k]x := a[k]x:=a[k] ; going down from j=k−1j = k - 1j=k−1 , move each a[j]>xa[j] > xa[j]>x one position to the right; then put xxx right after the first a[j]≤xa[j] \le xa[j]≤x (or into a[1]a[1]a[1] if there is none). x:=a[k]j:=k−1while (j≠0 and x<a[j])a[j+1]:=a[j]j:=j−1end whilea[j+1]:=x\begin{array}{l} x := a[k] \\ j := k - 1 \\ \textbf{while } (j \ne 0 \text{ and } x < a[j]) \\ \quad a[j + 1] := a[j] \\ \quad j := j - 1 \\ \textbf{end while} \\ a[j + 1] := x \end{array}x:=a[k]j:=k−1w…
[Algorithm Efficiency I] Apply insertion sort to the array 6,3,5,7,26, 3, 5, 7, 26,3,5,7,2 . What is the array after each step?
3,6,5,7,2 → 3,5,6,7,2 → 3,5,6,7,2 → 2,3,5,6,73, 6, 5, 7, 2 \ \to\ 3, 5, 6, 7, 2 \ \to\ 3, 5, 6, 7, 2 \ \to\ 2, 3, 5, 6, 73,6,5,7,2 → 3,5,6,7,2 → 3,5,6,7,2 → 2,3,5,6,7 In the third step 7 is inserted, and 7 is already at least as large as 6, so nothing moves.
[Algorithm Efficiency I] Insertion sort on 6,3,5,7,26, 3, 5, 7, 26,3,5,7,2 has reached 3,5,6,7,23, 5, 6, 7, 23,5,6,7,2 .In the last step ( k=5k = 5k=5 , x=2x = 2x=2 ), which values does jjj take, and what happens to the array?
j=4,3,2,1,0j = 4, 3, 2, 1, 0j=4,3,2,1,0 : 7, 6, 5 and 3 each move one position to the right, and then a[1]:=2a[1] := 2a[1]:=2 . Trace table of the whole run: each column shows the variables that change, from left to right.
[Algorithm Efficiency I] Insertion sort makes 2 comparisons ( j≠0j \ne 0j=0 and x<a[j]x < a[j]x<a[j] ) in each attempted iteration of its while loop. What is the maximum number of comparisons for an array of nnn items, and the worst-case order?
n2+n−2n^2 + n - 2n2+n−2 comparisons; worst-case order Θ(n2)\Theta(n^2)Θ(n2) . Placing a[k]a[k]a[k] takes at most kkk attempted iterations (when a[k]a[k]a[k] is less than all of a[1],…,a[k−1]a[1], \dots, a[k - 1]a[1],…,a[k−1] ), so at most 2k2k2k comparisons. Total: 2(2+3+⋯+n)=2(n(n+1)2−1)=n2+n−22(2 + 3 + \dots + n) = 2\left(\frac{n(n + 1)}{2} - 1\right) = n^2 + n - 22(2+3+⋯+n)=2(2n(n+1)−1)=n2+n−2 .The maximum occurs when the array is in reverse order.Example: n=5n = 5n=5 : 25+5−2=2825 + 5 - 2…
[Algorithm Efficiency I] The average-case analysis of insertion sort makes an assumption about where a[k]a[k]a[k] belongs among the first kkk positions. What is it, and what expected number of comparisons does it give for placing a[k]a[k]a[k] ?
a[k]a[k]a[k] is equally likely to belong in each of the first kkk positions; the expected number of comparisons is k+1k + 1k+1 . Position jjj needs k−j+1k - j + 1k−j+1 attempted iterations, so 2(k−j+1)2(k - j + 1)2(k−j+1) comparisons, with probability 1k\frac1kk1 : ∑j=1k1k⋅2(k−j+1)=2k⋅k(k+1)2=k+1\displaystyle\sum_{j=1}^{k} \frac1k \cdot 2(k - j + 1) = \frac2k \cdot \frac{k(k + 1)}{2} = k + 1j=1∑kk1⋅2(k−j+1)=k2⋅2k(k+1)=k+1 .Example: k=2k = 2k=2 : positions 1 and 2 need 4 and 2 comparisons,…
[Algorithm Efficiency I] EnE_nEn is the average number of comparisons insertion sort makes on an array of nnn items. What recurrence and closed formula hold for EnE_nEn , and what is the average-case order?
E1=0E_1 = 0E1=0 , Ek=Ek−1+k+1E_k = E_{k-1} + k + 1Ek=Ek−1+k+1 for k≥2k \ge 2k≥2 ; so En=n2+3n−42E_n = \frac{n^2 + 3n - 4}{2}En=2n2+3n−4 , and the average-case order is Θ(n2)\Theta(n^2)Θ(n2) . Sorting a[1],…,a[k]a[1], \dots, a[k]a[1],…,a[k] means sorting a[1],…,a[k−1]a[1], \dots, a[k - 1]a[1],…,a[k−1] and then placing a[k]a[k]a[k] , which takes k+1k + 1k+1 comparisons on average. E1=0E_1 = 0E1=0 because one item needs no step.Example: E2=3E_2 = 3E2=3 and E3=3+4=7=9+9−42E_3 = 3 + 4 = 7 = \…
[Algorithm Efficiency I] What are the worst-case and the average-case orders of insertion sort?
Both Θ(n2)\Theta(n^2)Θ(n2) . Worst case: n2+n−2n^2 + n - 2n2+n−2 comparisons; average case: n2+3n−42=12n2+32n−2\frac{n^2 + 3n - 4}{2} = \frac12 n^2 + \frac32 n - 22n2+3n−4=21n2+23n−2 comparisons.
[Exponential and Logarithmic Functions] Algorithms whose execution times are logarithmic functions of the input size, and algorithms whose execution times are exponential functions of it: which are efficient for large data sets?
Logarithmic: relatively efficient. Exponential: quite inefficient. Example: for input size n=1024n = 1024n=1024 , log2n=10\log_2 n = 10log2n=10 , while 2n2^n2n has 309 decimal digits.
[Exponential and Logarithmic Functions] What is the exponential function with base bbb ( b>0b > 0b>0 )?
The function that assigns to each real number xxx the value bxb^xbx . Example: base 2: 23=82^3 = 823=8 , 2−1=0.5\ 2^{-1} = 0.5 2−1=0.5 , 20.5≈1.414\ 2^{0.5} \approx 1.414 20.5≈1.414 .
[Exponential and Logarithmic Functions] Let 0<b<10 < b < 10<b<1 . How is the graph of y=bxy = b^xy=bx related to the graph of y=(1/b)xy = (1/b)^xy=(1/b)x ?
It is the reflection of the graph of y=(1/b)xy = (1/b)^xy=(1/b)x across the vertical axis. bx=(1/b)−xb^x = (1/b)^{-x}bx=(1/b)−x , and 1/b>11/b > 11/b>1 , so every exponential graph has one of these two shapes: Example: (1/2)−1=2=21(1/2)^{-1} = 2 = 2^{1}(1/2)−1=2=21 .
[Exponential and Logarithmic Functions] What are the domain and the range of any exponential function x↦bxx \mapsto b^xx↦bx ?
Domain: all real numbers. Range: all positive real numbers. Example: 2x>02^x > 02x>0 for every real xxx , and every y>0y > 0y>0 equals 2log2y2^{\log_2 y}2log2y .
[Exponential and Logarithmic Functions] Who first introduced logarithms, and who made them widely used?
The Scotsman John Napier (1550–1617). Astronomers and navigators adopted them because they reduced the time needed for multiplication and division. Today logarithms are used primarily as conceptual tools, since computers do the computations.
[Exponential and Logarithmic Functions] What is the logarithmic function with base bbb , logb:R+→R\log_b: \mathbf{R}^+ \to \mathbf{R}logb:R+→R ( b>0b > 0b>0 , b≠1b \neq 1b=1 )?
The function that assigns to each positive real xxx the number logbx\log_b xlogbx , the exponent to which bbb must be raised to obtain xxx . Example: log28=3\log_2 8 = 3log28=3 because 23=82^3 = 823=8 ; log100.01=−2\ \log_{10} 0.01 = -2 log100.01=−2 .
[Exponential and Logarithmic Functions] How are the graphs of y=logbxy = \log_b xy=logbx and y=bxy = b^xy=bx related?
They are symmetric with respect to the line y=xy = xy=x , because logb\log_blogb is the inverse of the exponential function with base bbb . Example: (3,8)(3, 8)(3,8) lies on y=2xy = 2^xy=2x and (8,3)(8, 3)(8,3) lies on y=log2xy = \log_2 xy=log2x .
[Exponential and Logarithmic Functions] What are the domain and the range of any logarithmic function logb\log_blogb ?
Domain: all positive real numbers. Range: all real numbers. Example: log20.5=−1\log_2 0.5 = -1log20.5=−1 , and log20\log_2 0log20 is not defined.
[Exponential and Logarithmic Functions] For b>1b > 1b>1 and positive reals x1<x2x_1 < x_2x1<x2 , how do logb(x1)\log_b(x_1)logb(x1) and logb(x2)\log_b(x_2)logb(x2) compare?
logb(x1)<logb(x2)\boldsymbol{\log_b(x_1) < \log_b(x_2)}logb(x1)<logb(x2) : for b>1b > 1b>1 the logarithmic function is increasing. Example: log24=2<3=log28\log_2 4 = 2 < 3 = \log_2 8log24=2<3=log28 .
[Exponential and Logarithmic Functions] log2(1024)= ?\log_2(1024) = \; ?log2(1024)=? and log2(1,048,576)= ?\log_2(1{,}048{,}576) = \; ?log2(1,048,576)=?
10 and 20. 210=10242^{10} = 1024210=1024 and 220=1,048,5762^{20} = 1{,}048{,}576220=1,048,576 . The logarithmic function grows very slowly, in contrast to the exponential function.
[Exponential and Logarithmic Functions] Let kkk be an integer and xxx a real number with 2k≤x<2k+12^k \le x < 2^{k+1}2k≤x<2k+1 . Then ⌊log2x⌋= ?\lfloor \log_2 x \rfloor = \; ?⌊log2x⌋=?
⌊log2x⌋=k\boldsymbol{\lfloor \log_2 x \rfloor = k}⌊log2x⌋=k In words: if xxx lies between two consecutive integer powers of 2, the floor of log2x\log_2 xlog2x is the exponent of the smaller power. Example: 8≤10<168 \le 10 < 168≤10<16 , so ⌊log210⌋=3\lfloor \log_2 10 \rfloor = 3⌊log210⌋=3 ( log210≈3.32\log_2 10 \approx 3.32log210≈3.32 ).
[Exponential and Logarithmic Functions] If kkk is an integer and 2k≤x<2k+12^k \le x < 2^{k+1}2k≤x<2k+1 , then ⌊log2x⌋=k\lfloor \log_2 x \rfloor = k⌊log2x⌋=k .How is this proved?
Apply the increasing function log2\log_2log2 to the inequalities: k≤log2x<k+1k \le \log_2 x < k + 1k≤log2x<k+1 . log2(2k)=k\log_2(2^k) = klog2(2k)=k and log2(2k+1)=k+1\log_2(2^{k+1}) = k + 1log2(2k+1)=k+1 . A real number between kkk (inclusive) and k+1k + 1k+1 (exclusive) has floor kkk by definition of the floor function.
[Exponential and Logarithmic Functions] For which integers n>1n > 1n>1 does ⌊log2(n−1)⌋=⌊log2n⌋\lfloor \log_2(n - 1) \rfloor = \lfloor \log_2 n \rfloor⌊log2(n−1)⌋=⌊log2n⌋ hold?
For every odd integer n>1n > 1n>1 . Example: n=9n = 9n=9 : ⌊log28⌋=3=⌊log29⌋\lfloor \log_2 8 \rfloor = 3 = \lfloor \log_2 9 \rfloor⌊log28⌋=3=⌊log29⌋ .Example: for even nnn it can fail: n=8n = 8n=8 gives ⌊log27⌋=2\lfloor \log_2 7 \rfloor = 2⌊log27⌋=2 but ⌊log28⌋=3\lfloor \log_2 8 \rfloor = 3⌊log28⌋=3 .
[Exponential and Logarithmic Functions] If kkk is an integer and 2k≤x<2k+12^k \le x < 2^{k+1}2k≤x<2k+1 , then ⌊log2x⌋=k\lfloor \log_2 x \rfloor = k⌊log2x⌋=k .Why is ⌊log2(n−1)⌋=⌊log2n⌋\lfloor \log_2(n - 1) \rfloor = \lfloor \log_2 n \rfloor⌊log2(n−1)⌋=⌊log2n⌋ for every odd integer n>1n > 1n>1 ?
An odd n>1n > 1n>1 is not a power of 2, so 2k<n<2k+12^k < n < 2^{k+1}2k<n<2k+1 for some integer k>0k > 0k>0 ; since 2k2^k2k and nnn are integers, also 2k≤n−1<2k+12^k \le n - 1 < 2^{k+1}2k≤n−1<2k+1 . The floor property applied to nnn and to n−1n - 1n−1 gives kkk both times.
[Exponential and Logarithmic Functions] How many binary digits are needed to represent a positive integer nnn ?
⌊log2n⌋+1\boldsymbol{\lfloor \log_2 n \rfloor + 1}⌊log2n⌋+1 Example: 8=100028 = 1000_28=10002 has ⌊log28⌋+1=4\lfloor \log_2 8 \rfloor + 1 = 4⌊log28⌋+1=4 digits; 7=11127 = 111_27=1112 has ⌊log27⌋+1=3\lfloor \log_2 7 \rfloor + 1 = 3⌊log27⌋+1=3 .
[Exponential and Logarithmic Functions] If kkk is an integer and 2k≤x<2k+12^k \le x < 2^{k+1}2k≤x<2k+1 , then ⌊log2x⌋=k\lfloor \log_2 x \rfloor = k⌊log2x⌋=k .Why does a positive integer nnn with binary representation 1ck−1⋯c1c01c_{k-1} \cdots c_1c_01ck−1⋯c1c0 ( k+1k + 1k+1 digits) satisfy k=⌊log2n⌋k = \lfloor \log_2 n \rfloork=⌊log2n⌋ ?
n=2k+ck−12k−1+⋯+c0n = 2^k + c_{k-1}2^{k-1} + \dots + c_0n=2k+ck−12k−1+⋯+c0 with each ci∈{0,1}c_i \in \{0, 1\}ci∈{0,1} , so 2k≤n≤2k+2k−1+⋯+1=2k+1−12^k \le n \le 2^k + 2^{k-1} + \dots + 1 = 2^{k+1} - 12k≤n≤2k+2k−1+⋯+1=2k+1−1 . The upper bound is the sum of a geometric sequence. So 2k≤n<2k+12^k \le n < 2^{k+1}2k≤n<2k+1 , and the floor property gives k=⌊log2n⌋k = \lfloor \log_2 n \rfloork=⌊log2n⌋ .
[Exponential and Logarithmic Functions] How many binary digits are needed to represent 52,83752{,}83752,837 , given log2(52,837)≈15.7\log_2(52{,}837) \approx 15.7log2(52,837)≈15.7 ?
16 ⌊15.7⌋+1=16\lfloor 15.7 \rfloor + 1 = 16⌊15.7⌋+1=16 . The logarithm is computed as log2(52,837)=log10(52,837)log102≈4.72290.3010\log_2(52{,}837) = \frac{\log_{10}(52{,}837)}{\log_{10} 2} \approx \frac{4.7229}{0.3010}log2(52,837)=log102log10(52,837)≈0.30104.7229 .Check: 215=32,768≤52,837<65,536=2162^{15} = 32{,}768 \le 52{,}837 < 65{,}536 = 2^{16}215=32,768≤52,837<65,536=216 .
[Exponential and Logarithmic Functions] A sequence is defined by a1=1a_1 = 1a1=1 and ak=2a⌊k/2⌋a_k = 2a_{\lfloor k/2 \rfloor}ak=2a⌊k/2⌋ for all integers k≥2k \ge 2k≥2 . What is an explicit formula for ana_nan ?
an=2⌊log2n⌋\boldsymbol{a_n = 2^{\lfloor \log_2 n \rfloor}}an=2⌊log2n⌋ for all integers n≥1n \ge 1n≥1 Example: a1,…,a8=1,2,2,4,4,4,4,8a_1, \dots, a_8 = 1, 2, 2, 4, 4, 4, 4, 8a1,…,a8=1,2,2,4,4,4,4,8 .
[Exponential and Logarithmic Functions] a1=1a_1 = 1a1=1 and ak=2a⌊k/2⌋a_k = 2a_{\lfloor k/2 \rfloor}ak=2a⌊k/2⌋ for all integers k≥2k \ge 2k≥2 .How does iteration lead to the guess an=2⌊log2n⌋a_n = 2^{\lfloor \log_2 n \rfloor}an=2⌊log2n⌋ ?
The computed terms show: if 2i≤n<2i+12^i \le n < 2^{i+1}2i≤n<2i+1 , then an=2ia_n = 2^ian=2i . And 2i≤n<2i+12^i \le n < 2^{i+1}2i≤n<2i+1 means i=⌊log2n⌋i = \lfloor \log_2 n \rfloori=⌊log2n⌋ . Example: a4=a5=a6=a7=4=22a_4 = a_5 = a_6 = a_7 = 4 = 2^2a4=a5=a6=a7=4=22 , and ⌊log2n⌋=2\lfloor \log_2 n \rfloor = 2⌊log2n⌋=2 for n=4,…,7n = 4, \dots, 7n=4,…,7 .
[Exponential and Logarithmic Functions] a1=1a_1 = 1a1=1 and ak=2a⌊k/2⌋a_k = 2a_{\lfloor k/2 \rfloor}ak=2a⌊k/2⌋ for k≥2k \ge 2k≥2 . Claim: an=2⌊log2n⌋a_n = 2^{\lfloor \log_2 n \rfloor}an=2⌊log2n⌋ for all n≥1n \ge 1n≥1 , proved by strong induction.In the inductive step for even kkk ( k+1k + 1k+1 odd), how is ak+1=2⌊log2(k+1)⌋a_{k+1} = 2^{\lfloor \log_2(k+1) \rfloor}ak+1=2⌊log2(k+1)⌋ obtained?
ak+1=2ak/2=2⋅2⌊log2k−1⌋=2⌊log2k⌋=2⌊log2(k+1)⌋a_{k+1} = 2a_{k/2} = 2 \cdot 2^{\lfloor \log_2 k - 1 \rfloor} = 2^{\lfloor \log_2 k \rfloor} = \boldsymbol{2^{\lfloor \log_2(k+1) \rfloor}}ak+1=2ak/2=2⋅2⌊log2k−1⌋=2⌊log2k⌋=2⌊log2(k+1)⌋ ⌊(k+1)/2⌋=k/2\lfloor (k+1)/2 \rfloor = k/2⌊(k+1)/2⌋=k/2 since k+1k + 1k+1 is odd; the inductive hypothesis applies to k/2k/2k/2 ; log2(k/2)=log2k−1\log_2(k/2) = \log_2 k - 1log2(k/2)=log2k−1 and ⌊x−1⌋=⌊x⌋−1\lfloor x - 1 \rfloor = \lfloor x \rfloor - 1⌊x−1⌋=…