For each pair of function listed below state if A(n) = O(B(n)), or B(n) = O(A(n))...

  

Transcribed Image Text:

For each pair of function listed below state if A(n) = O(B(n)), or B(n) = O(A(n)) or A(n) = (B(n)). Justify your answer. A(n)= n0 and B(n) = n log00 n A(n) = n log n and B(n) = n ln n A(n) = 2log n and B(n) = 100n . Solve the following recurrences. Justify your answer. T(n)= 3T(n/4) + O(n) T(n) = 5T(n/5) + O(n) T(n) = 2T(n/2) + n . For all the following statements, say if they are TRUE or FALSE. Justify your answer. Merge-Sort runs in linear time Quick-Sort runs in O(n log n) in the worst case Bubble-Sort runs in quadratic time in the worst case You are given n integers in the range 0 to k. Your goal is to build a data structure D that allows to answer any query about how many of the n integers fall into a particular range [a, b] in constant time. Show how to build such data structure in O(n + k) time. Example: Your have 15 integers between 0 and k = 7. Let them be [7,5,2,3,2,1,5,6,4,7,0,4, 1, 5,3] When you query [3, 6] the algorithm should return 8 (since there are that many integers between 3 and 6). Hint: Use a modification of Counting-Sort. Problem 5 Consider a hash table of size m with n values in it where collisions are resolved by chaining. Assuming Simple Uniform Hashing each slot will have an expected chain of length a = n/m Remember that in this case Insertion costs O(1) and Search and Delete cost o(a). Now assume that you want to keep the lists in sorted order. How would those costs change? For each pair of function listed below state if A(n) = O(B(n)), or B(n) = O(A(n)) or A(n) = (B(n)). Justify your answer. A(n)= n0 and B(n) = n log00 n A(n) = n log n and B(n) = n ln n A(n) = 2log n and B(n) = 100n . Solve the following recurrences. Justify your answer. T(n)= 3T(n/4) + O(n) T(n) = 5T(n/5) + O(n) T(n) = 2T(n/2) + n . For all the following statements, say if they are TRUE or FALSE. Justify your answer. Merge-Sort runs in linear time Quick-Sort runs in O(n log n) in the worst case Bubble-Sort runs in quadratic time in the worst case You are given n integers in the range 0 to k. Your goal is to build a data structure D that allows to answer any query about how many of the n integers fall into a particular range [a, b] in constant time. Show how to build such data structure in O(n + k) time. Example: Your have 15 integers between 0 and k = 7. Let them be [7,5,2,3,2,1,5,6,4,7,0,4, 1, 5,3] When you query [3, 6] the algorithm should return 8 (since there are that many integers between 3 and 6). Hint: Use a modification of Counting-Sort. Problem 5 Consider a hash table of size m with n values in it where collisions are resolved by chaining. Assuming Simple Uniform Hashing each slot will have an expected chain of length a = n/m Remember that in this case Insertion costs O(1) and Search and Delete cost o(a). Now assume that you want to keep the lists in sorted order. How would those costs change?

Answer rating: 100% (QA)

Answer Comparing An and Bn An n10 Bn n logn Answer An OBn Justification In the big O notation n10 gr... View the full answer