lllellts, prove that T (n) O(n). 6.101 P arrays With a total then 3: else if m 0

Question

lllellts, prove that T (n) O(n). 6.101 P arrays With a total then 3: else if m 0 Consider the recurrence for the running time of mergesort 4: return X (again, see Figure 6.42): 5: else if XL1] YL1] then 6: return X111 followed by merge (X12 and Prove that T (n) S T(n') if n S n 7: else that is, T is monotonic 8: return YL1] followed by merge (X,Y12 mil 6.102 Here is a recurrence relation for the number of comparisons d of size n (once again, see Figure 6.42): by mergesort on an input array Figure 6.42: The merging" of two sorted arrays. (For ease, C(1) 0 and C (n) 2C(n/2) n -1 n log n n we'll assume that n is a power of two.) Explain the recurrence relation, and then prove that C(n) 1 by induction The next few g(r) exercises refer to the algorithms in Figure 6.43, both which solve the f(n) same problem 1: if n 1 then. 1: if n 1 then 6.103 Give and solve (using induction) a recurrence relation for the running time of f return n return n 3: else 3: else Give a recurrence relation for g, and use it to prove that g (n' runs 4: return f(n 2) 6.104 in O(og n) time. while n 2x 6.105 Describe the set of input values n that cause the worst behavior for g(n) return g(n What problem do f and g solve? Prove your answer 6.106 Figure 6.43: Two algorithms Two copies of an out-of print book were listed online by Seller A and Seller B. Their prices were ea over $1,000,000 0, and they kept going up. By watching the prices over several days, it Exercises 6,107- became clear that the two sellers were using algorithms to set their prices in response to each other. 6.108 are based Let an and bn be the prices on day n by Seller A and B, respectively. The prices were set by two (badly on a story from conceived algorithms such that a n-1 and bon an where a 0.9983 and B Michael Eisen's Suppose that bo 1. Find the closed form solution for an and br. Prove your answer 6.107 blog post "Ama 6.108 State a necessary and sufficient condition on a, B, and bo such that a O(1) and b e(1) zon's $23,698,655.93 book about flies

Explanation / Answer

6.104: Give recurrence relation for G, and use it to prove that g(n) runs in O(log2 n) times.
Lets assume n=10,So g(10) For Given recursive algo. ?

Call Func. with n = 10

Call with n = 2

Call with n = 0

So, In all recursive function ran for Only 2 Instance . if we except the third false condition.

So, O(log2 n) = O(log2 10) = ~2

So, it is prove that g(n) runs in O(log2 n) times.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.