My goal is to write an algorithm that checks if an unsorted array of positive integers contains a value x and x^2 and return their indices if so. I've solved this by proposing that first you sort the array using merge sort, then perform binary search for x, then perform binary search for x^2. I then wrote that "since binary search has worst-case runtime of O(log n) and merge sort has worst-case runtime of O(n log n), we conclude that the worst-case runtime of this algorithm is O(n log n)." Am I correct in my understanding that when analyzing the overall efficiency of an algorithm that involves steps with different runtimes, we just take the one with the longest runtime? Or is it more involved than this? Thanks in advance!

CodePudding user response：

Since O(log n) < O(n log n):

O(n log n) O(log n) O(log n) = O(n log n)

So the time complexity of the hole algorithm is O(n log n).

CodePudding user response：

Your question is a bit ambigous. Do you get

1. an unsorted list [a,b,c ...] and a specific x to search for as parameter?

or

2. just get the list and have to find if there is at least one pair (x,y) with x^2 = y contained in the list?

If the first, the answer is O(n), because you just have to iterate over the list (no need to sort) and check for each element if it's equal to x or x^2. If you find both, the list fulfills the condition.

function match(list, x) {
  let foundX = false, foundX2 = false;
  for (let i of list) {
    if (i == x) foundX = true;
    else if (i == x*x) foundX2 = true;
  }
  return foundX && foundX2;
}    

If it's the second, the answer is O(n logn) because you sort the array first, and then iterate over the list and check if you can find the square of the current element. Sorting is O(n logn), binary search is O(logn), but as you apply it n times, you the overall searching is als O(n logn). Thus the overall complexity is O(n logn) O(n logn) or simply O(n logn).

function match(list) {
  list.sort();
  for (let i of list) {
    if (binsearch(list, i*i)) return true;
  }    
  return false;
}