Onetone Blog

4.1 Divisibility and Modular Arithmetic

$Division • Definition ○ If a and b are integers with a ≠ 0, ○ then a divides b if there exists an integer c such that b = ac. ○ When a divides b we say that a is a factor or divisor of b and that b is a multiple of a. ○ The notation a | b denotes that a divides b. ○ If a | b, then b/a is an integer. ○ If a does not divide b, we write a ∤ b. • Example ○ Determine whether 3 | 7 and whether 3 | 12. ○ 3 | 7 is false ○ 3 | 12 is true Properties of Divisibility • Theorem 1: Let a, b, and c be integers, where a ≠0. ○ If a | b and a | c, then a | (b + c); ○ If a | b, then a | bc for all integers c; ○ If a | b and b | c, then a | c. • Proof (i) ○ Suppose a | b and a | c, then it follows that ○ there are integers s and t with b = as and c = at. ○ Hence, b + c = as + at = a(s + t). ○ Hence, a | (b + c) • Corollary ○ If a, b, and c be integers, where a ≠0, such that a | b and a | c, ○ then a | mb + nc whenever m and n are integers. Division Algorithm • When an integer is divided by a positive integer, there is a quotient and a remainder. • This is traditionally called the “Division Algorithm,” but is really a theorem. • Division Algorithm ○ If a is an integer and d a positive integer, then ○ there are unique integers q and r, with 0 ≤ r d, such that ○ a = dq + r ○ d is called the divisor. ○ a is called the dividend. ○ q is called the quotient. ○ r is called the remainder. • Example: What are the quotient and reminder when 101 is divided by 11? ○ 101=11⋅9+2 ○ Thus the quotient is 9, and the remainder is 2 ○ 101 div 11 = 9 ○ 101 mod 11 = 2 • Example: What are the quotient and reminder when -11 is divided by 3? ○ −11=3⋅(−4)+1 Congruence Relation • Definition ○ If a and b are integers and m is a positive integer, ○ then a is congruent to b modulo m if m divides a – b. ○ The notation a ≡ b (mod m) says that a is congruent to b modulo m. ○ We say that a ≡ b (mod m) is a congruence and that m is its modulus. ○ Two integers are congruent mod m if and only if they have the same remainder when divided by m. ○ If a is not congruent to b modulo m, we write a ≢ b (mod m) • Determine whether 17 is congruent to 5 modulo 6 ○ 17 ≡ 5 (mod 6) because 6 divides 17 − 5 = 12. • Determine whether 24 and 14 are congruent modulo 6. ○ 24 ≢ 14 (mod 6) since 24 − 14 = 10 is not divisible by 6. The Relationship between (mod m) and mod m Notations • The use of “mod” in a ≡ b (mod m) and a mod m = b are different. ○ a ≡ b (mod m) is a relation on the set of integers. ○ In a mod m = b, the notation mod denotes a function. • The relationship between these notations is made clear in this theorem. • Theorem 3 ○ Let a and b be integers, and let m be a positive integer. ○ Then a ≡ b (mod m) if and only if ○ a mod m = b mod m. More on Congruence • Theorem 4 ○ Let m be a positive integer. ○ The integers a and b are congruent modulo m if and only if ○ there is an integer k such that a = b + km. • Proof: ○ If a ≡ b (mod m), then (by the definition of congruence) m | a – b. ○ Hence, there is an integer k such that a – b = km and equivalently a = b + km. ○ Conversely, if there is an integer k such that a = b + km, then km = a – b. ○ Hence, m | a – b and a ≡ b (mod m). Congruence of Sums and Products • Theorem 5 ○ Let m be a positive integer. ○ If a ≡ b (mod m) and c ≡ d (mod m), then § a + c ≡ b + d (mod m) § ac ≡ bd (mod m) • Proof: ○ Because a ≡ b (mod m) and c ≡ d (mod m) ○ by Theorem 4 there are integers s and t with b = a + sm and d = c + tm. ○ Therefore, § b + d = (a + sm) + (c + tm) = (a + c) + m(s + t) and § b d = (a + sm) (c + tm) = ac + m(at + cs + stm). ○ Hence, a + c ≡ b + d (mod m) and ac ≡ bd (mod m). • Example ○ Because 7 ≡ 2 (mod 5) and 11 ≡ 1 (mod 5) , it follows from Theorem 5 that ○ 18 = 7 + 11 ≡ 2 + 1 = 3 (mod 5) ○ 77 = 7 ∙ 11 ≡ 2 ∙ 1 = 2 (mod 5) Algebraic Manipulation of Congruence • Multiplying both sides of a valid congruence by an integer preserves validity. ○ If a ≡ b (mod m) holds then c∙a ≡ c∙b (mod m), where c is any integer, ○ holds by Theorem 5 with d = c. • Adding an integer to both sides of a valid congruence preserves validity. ○ If a ≡ b (mod m) holds then c + a ≡ c + b (mod m), where c is any integer, ○ holds by Theorem 5 with d = c. • Dividing a congruence by an integer does not always produce a valid congruence. ○ The congruence 14≡ 8 (mod 6) holds. ○ But dividing both sides by 2 does not produce a valid congruence since ○ 14/2 = 7 and 8/2 = 4, but 7≢4 (mod 6). Computing the mod m Function of Products and Sums • We use the following corollary to Theorem 5 to compute the remainder of the product or sum of two integers when divided by m from the remainders when each is divided by m. • Corollary: Let m be a positive integer and let a and b be integers. Then ○ (a + b) (mod m) = ((a mod m) + (b mod m)) mod m ○ ab mod m = ((a mod m) (b mod m)) mod m. Arithmetic Modulo m • Definitions ○ Let Zm be the set of nonnegative integers less than m: {0,1, …., m−1} ○ The operation +m is defined as a +_m b = (a + b) mod m. ○ This is addition modulo m. ○ The operation ∙m is defined as a ∙_m b = (a ∙ b) mod m. ○ This is multiplication modulo m. • Example: Find 7 +_11 9 and 7 ∙_11 9. ○ 7 +_11 9 = (7 + 9) mod 11 = 16 mod 11 = 5 ○ 7 ∙_11 9 = (7 ∙ 9) mod 11 = 63 mod 11 = 8 • The operations +_m and ∙_m satisfy many of the same properties as ordinary addition and multiplication. ○ Closure § If a and b belong to Zm , then a +_m b and a ∙_m b belong to Zm. ○ Associativity § If a, b, and c belong to Zm , then § (a +_m b) +_m c = a +_m (b +_m c) § (a ∙_m b) ∙_m c = a ∙_m (b ∙_m c). ○ Commutativity § If a and b belong to Zm , then § a +_m b = b +_m a § a ∙_m b = b ∙_m a. ○ Identity elements § The elements 0 and 1 are identity elements for addition and multiplication modulo m, respectively. § If a belongs to Zm , then a +_m 0 = a and a ∙_m 1 = a. ○ Additive inverses § If a≠ 0 belongs to Zm § then m − a is the additive inverse of a modulo m § and 0 is its own additive inverse. § a +_m (m− a) = 0 § 0 +_m 0 = 0 ○ Distributivity § If a, b, and c belong to Zm , then § a ∙_m (b +_m c) = (a ∙_m b) +_m (a ∙_m c) § (a +_m b) ∙_m c = (a ∙_m c) +_m (b ∙_m c). • Multiplicative inverses have not been included since they do not always exist. • For example, there is no multiplicative inverse of 2 modulo 6. • Using the terminology of abstract algebra ○ Zm with +_m is a commutative group ○ Zm with +_m and ∙_m is a commutative ring$

Math 521 – 2/28

$Convergence and Divergence • Definition ○ A sequence {p_n } in a metric space X converges to a point p∈X if ○ Given any ε 0, ∃N∈N s.t. d(p,p_n ) ε, ∀n≥N ○ If {p_n } converges to p, we write § p_n→p § lim_(n→∞)⁡〖p_n 〗=p § lim⁡〖p_n 〗=p ○ If {p_n } does not converge, it is said to diverge • Intuition ○ ε is small ○ N is a "point of no return" beyond which sequence is within ε of p Range and Bounded • Range ○ Given a sequence {p_n } ○ The set of points p_n (n∈N) is called the range of the sequence ○ Range could be infinite, but it is always at most countable ○ Since we can always construct a function f:N→{p_n }, where f(n)=p_n • Bounded ○ A sequence {p_n } is said to be bounded if its range is bounded Examples • Consider the following sequences of complex numbers {s_n } Limit Range Bounded s_n=1/n 0 Infinite Yes s_n=n^2 Divergent Infinite No s_n=1+(−1)^n/n 1 Infinite Yes s_n=i^n Divergent {±1,±i} Yes s_n=1 1 {1} Yes • Proof:lim_(n→∞)⁡〖1/n〗=0 ○ Let ε 0 ○ By Archimedean Property, we can choose N∈N s.t. N 1/ε ○ ∀n≥N, n 1/ε⇒1/n ε ○ i.e. d(1/n,0)=|1/n| ε,∀n≥N ○ Therefore lim_(n→∞)⁡〖1/n〗=0$

Math 541 – 2/28

$Coset • If G is a group, H≤G, and g∈G • Define gH≔{ghhH} • Similarly, define Hg≔{h�│hH} • gH is caleld a left coset, and Hg is called a right coset • An element of a coset is called a representative of the coset Proposition 22: Properties of Coset • Let G be a group and H≤G, then • For g_1,g_2∈G,g_1 H=g_2 H⟺g_2^(−1) g_1∈H ○ (⟹) Choose h∈H s.t. g_1=g_2 h (since g_1=g_1⋅1∈g_1 H=g_2 H) ○ Therefore g_2^(−1) g_1=h∈H ○ (⟸) Choose h∈H s.t. g_1=g_2 h ○ ∀h′∈H, g_1 h′=g_2 ⏟(h^′ )┬(∈H)∈g_2 H⇒g_1 H⊆g_2 H ○ ∀h′∈H,g_2 h′=g_1 ⏟(h(−1) h′ )┬(∈H)∈g_1 H⇒g_2 H⊆g_1 H ○ Therefore g_1 H=g_2 H • The relation ~ on G given by g_1~g_2 iff g_1∈g_2 H is a equivlance relation ○ Reflexive § If g∈G, then g=g⋅1∈gH § So g~g ○ Symmetric § If g_1,g_2∈G, and g_1~g_2 i.e. g_1∈g_2 H, then § g_1=g_2 h for some h∈H § Thus g_1 h(−1)=g_2 § So g_2∈g_1 H, which means g_2~g_1 ○ Transitive § Suppose g_1~g_2 and g_2~g_3 § This means g_1∈g_2 H and g_2∈g_3 H § Choose h1,h2∈H s.t. g_1=g_2 h, and g_2=g_3 h § Then g_1=g_3 h2 h1∈g_3 H § So g_1~g_2 • In particular, left/right cosets are either equal or disjoint ○ Suppose g_1,g_2∈G, and z∈g_1 H∩g_2 H ○ Suppose x∈g_1 H, then x~g_1~z~g_2 ○ So x∈g_2 H ○ This implies that g_1 H⊆g_2 H ○ To get g_2 H⊆g_1 H, exchange the roles of g_1 and g_2 ○ Therefore g_1 H=g_2 H • Example 1 ○ Let G be a group, H≤G. If h∈H, then hH=H ○ Let h′∈H, then h′=h(h(−1) h′ )∈hH ○ Thus H⊆hH ○ By closure under the operation, hH⊆H ○ Therefore hH=H • Example 2 ○ Let G=Z\/6Z, and H= unique subgroup of Z\/6Z of order 2 ○ H={0 ̅,3 ̅ }≤Z\/6Z ○ Left cosets of H in G § 0 ̅+{0 ̅,3 ̅ }={0 ̅,3 ̅ } § 1 ̅+{0 ̅,3 ̅ }={1 ̅,4 ̅ } § 2 ̅+{0 ̅,3 ̅ }={2 ̅,5 ̅ } § 3 ̅+{0 ̅,3 ̅ }={0 ̅,3 ̅ } § 4 ̅+{0 ̅,3 ̅ }={1 ̅,4 ̅ } § 5 ̅+{0 ̅,3 ̅ }={2 ̅,5 ̅ } ○ Note § |G|=6, |H|=2, and H has 3 distinct cosets (2⋅3=6) § If G is a finite group, and H≤G, then ├ |H|┤|├ |G|┤, and § H has |G|/|H| distinct left (or right) cosets in G Normal Subgroup • Definition ○ Let G be a group, let N≤G ○ N is a normal subgroup if gng^(−1)∈N, ∀n∈N,∀g∈G ○ In other words, N is closed under conjugation ○ If N≤G is normal, we write N⊴G • Example 1 ○ If G is abelian, every subgroup of G is normal ○ Suppose H≤G ○ Let h∈H and g∈G ○ Thus ghg^(−1)=hgg^(−1)=h∈H • Example 2 ○ Let G=S_3, H=⟨(1 2)⟩ ○ Suppose g=(1 2 3), h=(1 2) ○ ghg^(−1)=(1 2 3)(1 2) (1 2 3)^(−1)=(1 2 3)(1 2)(1 3 2)=(2 3)∉H ○ Therefore H⋬G • Example 3 ○ ⟨(1 2 3)⟩ in S_3 is normal • Example 4 ○ Let G=GL_n (R ○ Let P,A∈G, then PAP^(−1) is change of basis matrix ○ Note: In GL_n (R, conjugation amounts to changing basis Proposition 23: Properties of Normal Subgroup • Statement ○ Let N be a subgroup of a group G ○ N⊴G iff gN=Ng,∀g∈G • Proof (⟹) ○ Suppose N⊴G ○ Let g∈G, n∈N ○ gn=gn(g^(−1) g)=⏟(gng^(−1) )┬(∈N) g∈Ng⇒gN⊆Ng ○ ng=(gg^(−1) )ng=g ⏟(g^(−1) ng)┬(∈N)∈gN⇒Ng⊆gN ○ Therefore gN=Ng • Proof (⟸) ○ Suppose gN=Ng,∀g∈G ○ Let g∈G,n∈N ○ We must show gng^(−1)∈N ○ Choose n^′∈N s.t. gn=n^′ g ○ Then gng^(−1)=n^′∈N ○ Therefore N⊴G • Example ○ Let f:G→H be a homomorphism, then ker⁡f⊴G ○ ker⁡f is a subgroup of G § ker⁡f≠∅, since f(1_G )=1_H § If k_1,k_2∈ker⁡f § f(k_1 k_2^(−1) )=f(k_1 )f(k_2 )^(−1)=1_H § Thus k_1 k_2^(−1)∈ker⁡f § Therefore ker⁡f≤G ○ ker⁡f is normal § Let g∈G,k∈ker⁡f § f(gkg^(−1) )=f(g)f(k)f(g)^(−1)=f(g)f(g)^(−1)=1_H § ⇒gkg^(−1)∈ker⁡f∎$

3.3 Complexity of Algorithms

The Complexity of Algorithms • Given an algorithm, how efficient is this algorithm for solving a problem given input of a particular size? • To answer this question, we ask: ○ How much time does this algorithm use to solve a problem? ○ How much computer memory does this algorithm use to solve a problem? • When we analyze the time the algorithm uses to solve the problem given input of a particular size, we are studying the time complexity of the algorithm. • When we analyze the computer memory the algorithm uses to solve the problem given input of a particular size, we are studying the space complexity of the algorithm. • In this course, we focus on time complexity. • The space complexity of algorithms is studied in later courses. • We will measure time complexity in terms of the number of operations an algorithm uses and we will use big-O and big-Theta notation to estimate the time complexity. • We can use this analysis to see whether it is practical to use this algorithm to solve problems with input of a particular size. • We can also compare the efficiency of different algorithms for solving the same problem. • We ignore implementation details because it is extremely complicated to consider them. Time Complexity • To analyze the time complexity of algorithms, we determine the number of operations, such as comparisons and arithmetic operations (addition, multiplication, etc.). • We can estimate the time a computer may actually use to solve a problem using the amount of time required to do basic operations. • We ignore minor details, such as the “house keeping” aspects of the algorithm. • We will focus on the worst-case time complexity of an algorithm. • This provides an upper bound on the number of operations an algorithm uses to solve a problem with input of a particular size. • It is usually much more difficult to determine the average case time complexity of an algorithm. • This is the average number of operations an algorithm uses to solve a problem over all inputs of a particular size. Complexity Analysis of Algorithms • Example: Describe the time complexity of the algorithm for finding the maximum element in a finite sequence. ○ Count the number of comparisons. ○ The max a_i comparison is made n − 1 times. ○ Each time i is incremented, a test is made to see if i≤n. ○ One last comparison determines that i>n. ○ Exactly 2(n−1)+1=2n−1 comparisons are made. ○ Hence, the time complexity of the algorithm is Θ(n). • Example: Determine the time complexity of the linear search algorithm. ○ Count the number of comparisons. ○ At each step two comparisons are made; i≤n and x≠a_i . ○ To end the loop, one comparison i≤n is made. ○ After the loop, one more i≤n comparison is made. ○ If x=a_i, 2i+1 comparisons are used. ○ If x is not on the list, 2n+1 comparisons are made and then an additional comparison is used to exit the loop. ○ So, in the worst case 2n+2 comparisons are made. ○ Hence, the complexity is Θ(n). • Example: Describe the average case performance of the linear search algorithm. ○ Assume the element is in the list and that the possible positions are equally likely. ○ By the argument on the previous slide, if x=a_i , the number of comparisons is 2i+1 ○ (3+5+7+…+(2n+1))/n=(2(1+2+3+…+n)+n)/n=2[n(n+1)/2]/n+1=n+2 ○ Hence, the average-case complexity of linear search is Θ(n). • Example: Describe the time complexity of binary search in terms of the number of comparisons used. ○ Assume (for simplicity) n = 2^k elements. Note that k=log⁡n. ○ Two comparisons are made at each stage; i<j, and x>a_m. ○ At the first iteration the size of the list is 2k and after the first iteration it is 2k−1. ○ Then 2k−2 and so on until the size of the list is 2^1=2. ○ At the last step, a comparison tells us that the size of the list is the size is 2^0=1 and the element is compared with the single remaining element. ○ Hence, at most 2k+2=2 log⁡n+2 comparisons are made. ○ Therefore, the time complexity is Θ (log⁡n), better than linear search. • Example: What is the worst-case complexity of bubble sort in terms of the number of comparisons made? ○ A sequence of n−1 passes is made through the list. ○ On each pass n−i comparisons are made. ○ (n−1)+(n−2)+…+2+1=n(n−1)/2=1/2 n^2−1/2 n ○ The worst-case complexity of bubble sort is Θ(n^2) • Example: What is the worst-case complexity of insertion sort in terms of the number of comparisons made? ○ The total number of comparisons are ○ 2+3+…+n=n(n−1)/2−1 ○ Therefore the complexity is Θ(n^2) • Example: How many additions of integers and multiplications of integers are used by the matrix multiplication algorithm to multiply two n×n matrices. ○ There are n^2 entries in the product. ○ Finding each entry requires n multiplications and n−1 additions. ○ Hence, n^3 multiplications and n^2 (n−1) additions are used. ○ Hence, the complexity of matrix multiplication is O(n^3). Understanding the Complexity of Algorithms Complexity of Problems • Tractable Problem ○ There exists a polynomial time algorithm to solve this problem. ○ These problems are said to belong to the Class P. • Intractable Problem ○ There does not exist a polynomial time algorithm to solve this problem • Unsolvable Problem ○ No algorithm exists to solve this problem, e.g., halting problem. • Class NP ○ Solution can be checked in polynomial time. ○ But no polynomial time algorithm has been found for finding a solution to problems in this class. • NP Complete Class ○ If you find a polynomial time algorithm for one member of the class, ○ it can be used to solve all the problems in the class. P Versus NP Problem • The P versus NP problem asks whether the class P = NP? • Are there problems whose solutions can be checked in polynomial time, but can not be solved in polynomial time? • Note that just because no one has found a polynomial time algorithm is different from showing that the problem can not be solved by a polynomial time algorithm. • If a polynomial time algorithm for any of the problems in the NP complete class were found, then that algorithm could be used to obtain a polynomial time algorithm for every problem in the NP complete class. • Satisfiability (in Section 1.3) is an NP complete problem. • It is generally believed that P≠NP since no one has been able to find a polynomial time algorithm for any of the problems in the NP complete class. • The problem of P versus NP remains one of the most famous unsolved problems in mathematics (including theoretical computer science). • The Clay Mathematics Institute has offered a prize of $1,000,000 for a solution.

3.2 The Growth of Functions

$The Growth of Functions • In both computer science and in mathematics, there are many times when we care about how fast a function grows. • In computer science, we want to understand how quickly an algorithm can solve a problem as the size of the input grows. ○ We can compare the efficiency of two different algorithms for solving the same problem. ○ We can also determine whether it is practical to use a particular algorithm as the input grows. ○ We’ll study these questions in Section 3.3. • Two of the areas of mathematics where questions about the growth of functions are studied are: ○ number theory (covered in Chapter 4) ○ combinatorics (covered in Chapters 6 and 8) Big-O Notation • Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. • We say that f(x) is O(g(x)) if there are constants C and k such that ○ |f(x)|≤C|g(x)| whenever xk. • This is read as “f(x) is big-O of g(x)” or “g asymptotically dominates f.” • The constants C and k are called witnesses to the relationship f(x) is O(g(x)). • Only one pair of witnesses is needed. Some Important Points about Big-O Notation • If one pair of witnesses is found, then there are infinitely many pairs. • We can always make the k or the C larger and still maintain the inequality |f(x)|≤C|g(x)| . • If f(x) is O(g(x)) and g(x) is O(hx)) then f(x) is O(hx)) • You may see “ f(x)=O(g(x))” instead of “ f(x) is O(g(x)).” • But this is an abuse of the equals sign since the meaning is that there is an inequality relating the values of f and g, for sufficiently large values of x. • It is ok to write f(x)∈O(g(x)), because O(g(x)) represents the set of functions that are O(g(x)). • Usually, we will drop the absolute value sign since we will always deal with functions that take on positive values. Using the Definition of Big-O Notation • Example: Show that f(x)=x^2+2x+1 is O(x^2 ). ○ Since when x1, xx^2 and 1x^2 ○ 0≤x^2+2x+1≤x^2+2x^2+x^2−4x^2 ○ Can take C = 4 and k = 1 as witnesses to show that f(x) is O(x^2 ) ○ Alternatively, when x2, we have 2x≤x^2 and 1x^2. ○ Hence, 0≤x^2+2x+1≤x^2+x^2+x^2=3x^2 when x2. ○ Can take C = 3 and k = 2 as witnesses instead. • Example: Show that 7x^2 is O(x^3) ○ When x7, 7x^2x^3. ○ Take C =1 and k = 7 as witnesses to establish that 7x^2 is O(x^3). ○ (Would C = 7 and k = 1 work?) Yes • Example: Show that n^2 is not O(n) ○ Suppose there are constants C and k for which n^2≤Cn, whenever nk. ○ Then n≤ C must hold for all nk. A contradiction! Big-O Estimates for Polynomials • Let f(x)=a_n x^n+a_(n−1) x^(n−1)+…+a_1 x+a_0 where a_0,a_1,…a_n are real numbers with a_n≠0 • Then f(x) is O(x_n). • |f(x)| = |a_n x^n + a_(n−1) x^(n−1)+…+a_1 x+a_0 | • ≤ |an|xn + |an−1| xn−1 + ∙∙∙ + |a1|x1 + |a0| • = x_n (|a_n |+|a_(n−1) |/x +…+|a1|/x_(n−1) +|a_0 |/x_n ) • ≤ x_n (|a_n |+ |a_(n−1) |+…+ |a_1 |+ |a_0 |) • Take C=|a_n |+|a_(n−1) |+…+ |a_0 | and k=1. • Then f(x) is O(x^n). • The leading term a_n x^n of a polynomial dominates its growth. Big-O Estimates for Some Important Functions • Example: Use big-O notation to estimate the sum of the first n positive integers. ○ 1+2+…+n≤n+n+…+n=n^2 ○ 1+2+…+n is O(n^2 ) taking C=1 and k=1 • Example: Use big-O notation to estimate the factorial function f(n)=n!=1×2×…×n ○ n!=1×2×…×n≤n×n×…×n^n ○ n! is O(n^n ) taking C=1 and k=1 • Example: Use big-O notation to estimate log⁡n! ○ Given that n!n^n ○ then log⁡n!≤n⋅log⁡n . ○ Hence, log⁡n! is O(n log⁡n ) taking C = 1 and k = 1. Display of Growth of Functions Combinations of Functions • If f_1 (x) is O(g_1 (x)) and f_2 (x) is O(g_2 (x)) then ○ (f_1+f_2)(x) is O(max⁡{|g_1 (x)|,|g_2 (x)|} ). • If f_1 (x) and f_2 (x) are both O(g(x)) then ○ (f_1+f_2)(x) is O(g(x)). • If f_1 (x) is O(g_1 (x)) and f_2 (x) is O(g_2 (x)) then ○ (f_1 f_2)(x) is O(g_1 (x) g_2 (x)). Big-Omega Notation • Let f and g be functions from the set of integers/real numbers to the set of real numbers. • We say that f(x) is Ω(g(x)) if there are constants C and k such that |f(x)|≥C|g(x)| when xk • We say that “f(x) is big-Omega of g(x).” • Big-O gives an upper bound on the growth of a function, while Big-Omega gives a lower bound. • Big-Omega tells us that a function grows at least as fast as another. • f(x) is Ω(g(x)) if and only if g(x) is O(f(x)). • This follows from the definitions. • Example: Show f(x)=8x^3+5x^2+7 is Ω(g(x)) where g(x)=x^3 ○ f(x)=8x^3+5x^2+7≥8x^3 for all positive real numbers x ○ Is it also the case that g(x)=x^3 is O(8x^3+5x^2+7)? Yes Big-Theta Notation • Let f and g be functions from the set of integers/real numbers to the set of real numbers. • The function f(x) is Θ(g(x)) if f(x) is O(g(x)) and f(x) is Ω(g(x)) • We say that ○ “f is big-Theta of g(x)” ○ “f(x) is of order g(x)” ○ “f(x) and g(x) are of the same order.” • f(x) is Θ(g(x)) if and only if there exists constants C_1, C_2 and k such that C_1 g(x)f(x)C_2 g(x) if xk. • This follows from the definitions of big-O and big-Omega. • When f(x) is Θ(g(x)) it must also be the case that g(x) is Θ(f(x)) • Note that f(x) is Θ(g(x)) if and only if it is the case that f(x) is O(g(x)) and g(x) is O(f(x)). • Sometimes writers are careless and write as if big-O notation has the same meaning as big-Theta. Examples of Big-Theta Notation • Example 1: Show that the sum of the first n positive integers is Θ(n^2 ) ○ Let f(n) = 1 + 2 + ∙∙∙ + n. ○ We have already shown that f(n) is O(n^2). ○ To show that f(n) is Ω(n^2), we need a positive constant C such that f(n) Cn^2 for sufficiently large n. ○ Summing only the terms greater than n/2 we obtain the inequality 1 + 2 + ∙∙∙ + n ≥ ⌈n/2⌉+(⌈n/2⌉+1)+…+n ≥ ⌈n/2⌉+⌈n/2⌉+…+⌈n/2⌉ = (n−⌈n/2⌉+1)⌈n/2⌉ ≥ (n/2)(n/2) = n^2/4 ○ Taking C = 1/4, f(n) Cn^2 for all positive integers n. ○ Hence, f(n) is Ω(n^2), and we can conclude that f(n) is Θ(n^2). • Example 2: Show that f(x)=3x^2+8x log⁡x is Θ(x^2) ○ f(x)=3x^2+8x log⁡x≤11x^2 for x 1, ○ since 0 ≤8x log⁡x≤ 8x^2. ○ Hence, 3x^2+8x log⁡x is O(x^2). ○ x^2 is clearly O(3x^2+8x log⁡x) ○ Hence, 3x^2+8x log⁡x is Θ(x^2)$

Shawn Zhong

Shawn Zhong

4.1 Divisibility and Modular Arithmetic

Math 521 – 2/28

Math 541 – 2/28

3.3 Complexity of Algorithms

3.2 The Growth of Functions

Search

WeChat Account