CMPS 211 Homework Solution 9, Fall 2014

Ayman Al Zaatari 11 December 2014 Assignment 9 Solution 1 Assignment 9 Solution Ex1: a)  18 <= x  17x + 11 <= 18x +x <= x2  17x + 11 <= C x2  f(x) ∊ O(x2) for k=18 and C=1  If f(x) ∉ Ω(x2)  17x + 11 > C x2 for C >0 and x >=k x > 18  18x >= 17x + x > 17x + 11  18x > Cx2 dividing by x, 18 > Cx => x < C1 , for C1 = C/18, but x > k => impossible f(x) ∉ Ω(x2) f(x) ∉ θ(x2) b)  x2 + 1000 ≤ 1000x2 for x>1000 f(x) ∊ O(x2) for C=1000 and k=1000  x2 + 1000 ≥ x2 for x>1000 f(x) ∊ Ω(x2) for C=1 and k=1000 f(x) ∊ θ(x2) for k=1000 c)  logx < x  x logx ≤ x2 for x > 1 f(x) ∊ O(x2) for k=1 and C=1  Assume f(x) ∊ Ω(x2)  xlogx >= C x2 such that C>0, |  logx >= Cx  logx/x >= C , but we know that the limit at infinity = 0,  false Assumption  f(x) ∉ Ω(x2) f(x) ∉ θ(x2) d)  x4/2 ≤ Cx2  x2 ≤ 2C  x <Sqrt(2C) f(x) ∉ O(x2)  x4/2 ≥ Cx2 => x2 ≥ 2C for C=1 and k=2 f(x) ∊ Ω(x2) for C=1 and k=2 Ayman Al Zaatari 11 December 2014 Assignment 9 Solution 2 f(x) ∉ θ(x2) e)  2x ≤ Cx2  x ≤ C + 2logx  x/2logx <= (C+1)/2logx…At infinity, the limits would be ∞ <= 0 which is false  f(x) ∉ O(x2)  2x ≥ Cx2 => x ≥ C + 2logx which is true for x > 10 and C = 1 f(x) ∊ Ω(x2) for C=1 and k=10 f(x) ∉ θ(x2) f) let x=a+ε for 0 <= ε < 1,  a2 ≤ ⌊x⌋·⌈x⌉ ≤ (a+1)2  a ≤ x ≤ a+1 a2 ≤ ⌊x⌋·⌈x⌉ ≤ (a+1)2 ≤ 3a2 ≤ Cx2 for x>1 f(x) ∊ O(x2) for C=3 and k=1  x2 = (a+ε) 2 = a2 + 2aε + ε2 >= a2 x2 ≤ ⌊x⌋·⌈x⌉ ≤ (a+1)2 f(x) ∊ Ω(x2) for C=1 and k=1 f(x) ∊ θ(x2) Ex2: 1000 log n, sqrt(𝑛), n log n, n2/1000000, 2n, 3n, 2n! Ex3: We can pick the function with highest order when we have addition, and give the multiplaction of the functions when we have mutliplication a) f(x) = O(n3) * O(logn) +O(17logn)*O(n3) = O(n3logn) b) f(x) = O(2n)*O(3n) = O(6n) c) f(x) = O(nn)*O(n!) = O(nn × n!) Ex4: a)  f(x) = x2, its obviously Θ(x2)  g(x) = 2x2 +x – 7, for x > 7 > -7  2x > x-7 > 0 and x2 > 2x  2x2 +x -7 <= 2x2 + 2x <= 4x2 Ayman Al Zaatari 11 December 2014 Assignment 9 Solution 3  g(x) is Θ(x2)  f and g are of same order b)  f(x) = x which is obviously Θ(x)  g(x) =⌊x+1/2⌋, consider 2 cases of x a. x = a + ε, and ε < 0.5, then ⌊x+1/2⌋ = a = x - ε, then its Θ(x) b. x = a + ε, and ε > 0.5, then ⌊x+1/2⌋ = a +1 = x +(1- ε), then its Θ(x) f and g are of same order c)  f(x) = log(x2) = 2logx which is obviously Θ(logx)  g(x) = log(x2+1) Need to prove: C1 logx <= log(x2+1) <= C2 logx 2C1logx <= 2log(x^2 +1) <= 2C2logx XC1 <= x2+1 <= XC2, which is true C1 = 0.5, C2 = 3, and x > 3  g is Θ(logx)  f and g are of same order d)  f(x) = log10x = log2x/ log210, which is obviously Θ(lgx)  g(x) = log2x, which is obviously Θ(lgx) f and g are of same order Ex5: Applying the following algorithm for getting will be done as follows: Step Previous Value Resulting Value 1 2 i i+1 k So, in K steps, we will have , so to calculate , we will need log(n) steps However, the naïve way for calculating , starting with 1, and multiplying by x, will need n steps instead of log(n)…so the first way is more efficient Ayman Al Zaatari 11 December 2014 Assignment 9 Solution 4 Ex6: 1 Day = 24 * 60 * 60 = 86400 seconds. a) (10-11)*logn = 86400 n=286400 E11 b) (10-11)*1000n = 86400 n=86.4×1011 c) (10-11)*n2 = 86400 n = sqrt(86400×1011) d) (10-11)*1000n2 = 86400 n = sqrt(86.4×1011) e) (10-11)*n3 = 86400 n = √ f) (10-11)*×2n = 86400 n = log(86400×1011) g) (10-11)*×22n = 86400 n = log(86400×1011)/2 h) (10-11)*× = 86400 n = log(log(86400×1011)) Ex8: procedure OccurMoreThanOnce (a1, a2, . . . , an: nondecreasing integers) for i:= 1 to n-1 while(i < n-1 && ai+1 = ai) i++ print(ai) if(n = 1 || an != an-1) print(an) The worst case complexity of this algorithm is Θ(n) Ex9: To check if a set of n talks can be scheduled together, we need Θ(nlgn) – Sort, then check if there are conflicts We have 2n subsets for n talks. Thus the running time will be O(nlgn * 2n) Ex10: -Linear search finds the value in O(n), so doubling the size will result in doubling the number of comparisons -Binary search find the value in O(lgn), so doubling the size will result in 1 extra comparison