3. Explain or describe the worst-case time complexity, measured in terms of comparisons, of t ternary search algorithm described below. Hint: Follow the way we compute the time complexity of Binary search algorithm procedure ternary search(s: integer, a₁,a2,..., an increasing integers) i:=1 j:= n while i < j - 1 1:= [(i+j)/3] u := [2(i+j)/3] if x > a, then i := u + 1 else if x > a then i:=1+1 j:= u else j := 1 if x = a; then location := i =j else if x = a; then location := else location :=0 return location 19 if not found)

3. Explain or describe the worst-case time complexity, measured in terms of comparisons, of t ternary search algorithm described below. Hint: Follow the way we compute the time complexity of Binary search algorithm procedure ternary search(s: integer, a₁,a2,..., an increasing integers) i:=1 j:= n while i < j - 1 1:= [(i+j)/3] u := [2(i+j)/3] if x > a, then i := u + 1 else if x > a then i:=1+1 j:= u else j := 1 if x = a; then location := i =j else if x = a; then location := else location :=0 return location 19 if not found)

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

,,,,,,
Considering the following algorithm, analyze its best case, worst case and average case time complexity in terms of a polynomial of n and the asymptotic notation of ɵ. You need to show the steps of your analysis.
Construct a Divide and Conquer-based algorithm for the following problem andanalyze the same in the worst case.Input: An ordered array L with n elements and item X that is to be searched inthe array L.Output: Index j where L[j]=X, if X is found or else j = 0, if X not found.
No plagarism please! Correct and detailed answer will be Upvoted else downvoted. Thank you!
*Data Structutures and Algorithm
a certain divide and conquer algorithm splits a problem into 16 sub-instances each of which is about one half of the original size it performs 3n^2 characteristic operations to do the splitting and combining. Let T(n) be the time complexity of the algorithm as a function of its input size n a) Determine a recurrence relation for T(n) b) Determine T's Big-0 complexity class using the master theorem.
1. Let S be a set of n arbitrary but distinct numbers. (a) Give a deterministic algorithm to output the largest n³/4 of the numbers in S in sorted order. Your algorithm must use O(n) comparisons. (b) Show that any deterministic comparison-based algorithm that correctly outputs the median on inputs of n distinct elements must use at least n 1 comparisons. To be completely precise, the median is defined to be the [n/2]th smallest element.
Find the running time for each of the following algorithms. Show work by finding a table of values for each while loop, writing the summations, then solving. Be sure to show work on both the upper bound and lower bound, justify the split, and check that the bounds differ by only a constant factor. Use asymptotic notation to write the answer. a) Func2(n) 1 2 3 4 5 6 7 S ← 0; j←7n²; while (j > 8) do s+ s + i- j; je lj/9]; end return (s);
(b) Consider the two sorting algorithms below, which each take as input array A] indexed from s to f. SwapSort2(A, s, f) SwapSort1(A, s, f) swapped = true while (swapped) swapped = false for i = s to f-2 swapped = true while (swapped) swapped = false for i = s to f-2 if A[i] > A[i+2] Swap A[i] and A[i+2] swapped = true if A[i] > Ali+2] Swap A[i] and A[i+2] swapped = true swapped = true while (swapped) swapped = false for i = s to f-1 if A[i] > A[i+1] Swap A[i] and A[i+1] swapped = true • Execute SwapSort1 on array A = [7,6, 5, 4, 3, 2, 1] indexed from s = 1 to f = 7. • Which of the above two algorithms is correct?. Justify your answer. • What is the worst-case number of comparisons are made by SwapSort2 when the input array A has length n and is sorted in reverse order? • Does your result from above represent the worst-case number of comparisons made by SwapSort2? Justify your answer. • Justify that the worst-case runtime of SwapSort2 is of the form T(n) a, b, c. = an? + bn +c for…
Basic Algorithms: Explain the MIN-MAX algorithm that can find the minimum and maximum in an array of n elements by using 3/2*n-2 comparisons. Show the computational complexity analysis
(a) Show that the computational complexity of Bubble Sort in the worst case is O(n2).
Find the function that best represents the temporal order of the following algorithms in the worst case.Count the operations of addition (+) and multiplication (×). Suppose that the array K contains n values.polyEval(K: whole array, x: whole): whole y ← K[n − 1] for i ← n − 2, n − 3 .. 0 y ← y × x + K[i] end for return y end polyEval justify your answer please