1. Given three arrays of N names each, describe an O(nlogn) algorithm to determine if there...

1. Given three arrays of N names each, describe an O(nlogn) algorithm

to determine if there is any name common to all three arrays, and if so, return the first such name.?

2. Given an input array with all equal values, compare the following sorting algorithm using big-O notation.

	Running Time	Space Complexity
Merge Sort
Quick Sort
Heap Sort

Solutions

Expert Solution

The following algorithm takes O(NlogN) in sorting and O(N +N +N) in finding the intersection of three arrays. Thus the total running time is O(NlogN), taking the dominant term.

The solution for 2. part is below: Note: the answers depend heavily on the implementation of the sorting algorithms.

venereology answered 3 months ago

Next > < Previous

Related Solutions

Q1. A. What is the complexity of partition process in quick sort? O(1) O(logN) O(N) O(NlogN)...

Q1. A. What is the complexity of partition process in quick sort? O(1) O(logN) O(N) O(NlogN) B. Evaluate the following postfix expression. 2 3 4 + * C. In an array representation of heap, what are the parent node of a node a[10]? a[9] a[11] a[5] a[20] There is no easy way to access parent node in such representation. D. In an array representation of heap, what are the children nodes (if any) of a node a[10]? a[11] and a[12]...

Describe an O(n)-time algorithm that checks if brackets in a given arithmetic expression is properly placed,...

Describe an O(n)-time algorithm that checks if brackets in a given arithmetic expression is properly placed, i.e., all left brackets are matched with their right counterparts and there are no unmatched brackets between any pair of matched brackets. Note that there are generally more than one types of brackets and only those of the same type can match against each other. For simplicity, you can assume that all operands are represented as ‘a’ and addition, +, is the only available...

prove using limit lemma that n^2 > nlogn given some epsilon > 0

Present an O(n) algorithm that sorts n positive integer numbers a1, a2, . . . ,...

Present an O(n) algorithm that sorts n positive integer numbers a1, a2, . . . , an which are known to be bounded by n 2 (so ai ≤ n 2 , for every i = 1, . . . , n. Use the idea of Radix Sort (discussed in class and presented in Section 8.3 in the textbook). Illustrate your algorithm by showing on paper similar to Fig. 8.3, page 198 in the textbook (make sure you indicate clearly...

(15 pts) Describe an O(n)-time algorithm that partitions a doubly linked list L into two doubly...

(15 pts) Describe an O(n)-time algorithm that partitions a doubly linked list L into two doubly linked lists L1 and L2, where L1 contains the odd-number-th elements in L and L2 contains the even-number-th elements in L. Elements in both L1 and L2 should appear in the same order as they appear in L. For example, if L contains the numbers 4, 7, 9, 1, and -3, in that order, then the output L1 should contain 4, 9, and -3,...

Divide and conquer problem. Suppose we are given two sorted arrays A[1 . . . n]...

Divide and conquer problem. Suppose we are given two sorted arrays A[1 . . . n] and B[1 . . . n] and an integer k. Describe an algorithm to find the kth smallest element in the union of A and B in O(log n) time. For example, if k = 1, your algorithm should return the smallest element of A ∪ B; if k = n, your algorithm should return the median of A ∪ B.) You can assume...

Question