Algorithms problem: Can use either quicksort, mergesort, insertion sort, binary

Question

Algorithms problem: Can use either quicksort, mergesort, insertion sort, binary search, selection sort, bubblesort, or quick select

Provide efficient algorithms for each of the problems below. You should describe the main idea in a few sentences and provide pseudo code. Your pseudocode can use any previously taught algorithm as a function call. Just specify what the call does and its time complexity. Also, write down the worst case complexities for your algorithms. Assume all arrays below are integer arrays. Given sorted arrays a and b, each of size n, do they have an element in common? Given a sorted array a of size m and an unsorted array b of size n, do they have an element in common? Your solution must not sort the array b. Given unsorted arrays a and b of size n, do they have an element in common? Your solution must avoid sorting either array. The rank of a given number e in an array a is the number of elements in a that are strictly less than e. Also, given array a, let minimum(a) represent the minimum element of a. Given unsorted arrays a and b of size n, find the rank of minimum(a) in the array b. Your solution must run in time (n).

Explanation / Answer

a).
Since both arraya are sorted and size is same. So to find common elements just
traverse both array and compare corresponding elements.

boolean isCommanElement(int a[], int b[], int n)
   for i=1 to n in a and b
       if a[i] ==b[i]
           return ture;
          
Time Complexity : O(n)

b).          
Here b is not sorted, but a is sorted. So, for every element of b we can do binary search
in a to check wether that element from b is present or not

boolean isCommanElement(int a[], int b[], int n)
   for i=1 to n in b
       int x = binarySearch(a, b[i])
       if(x != -1) // element found
           return true;
          
Time Complexity = O(nlogn)

c).
Since both array is unsorted, So for every element of a we can search in binary
boolean isCommanElement(int a[], int b[], int n)
   for i=1 to n in a
       for j=1 to n in b
           if a[i] == b[j]
               return true
              
Time Complexity = O(n^2)

d). To find rank of minimum(a), we traverse array b and compare every element of b with minimum(a),
   if element of b is less than minimum(a), we increase count

int rank(int a[], int b[], int n)
   int count = 0
   int min = minimum(a)
   for i=1 to n in b:
       if b[i] < min:
           count= count +1
   return count;
  
Time Complexity = O(n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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