CODEWITHSUNDEEP
algorithmsortingtime-complexitybig-oamortized-analysis
liatkatz
liatkatz

Reputation: 71

Worst-case time complexity of an algorithm with 2+ steps

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!

Upvotes: 0

Views: 83

Answers (2)

derpirscher
derpirscher

Reputation: 17436

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

  1. 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?

Now as you have cleared it's the first, the answer is O(n), because you just have to iterate over the list (no need to sort or binary search) 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 ix = -1, ixx = -1;
  for (let i = 0; i< list.length && (ix == -1 || ixx == -1); i++) {
    if (i == x) ix = i;
    if (i == x*x) ixx = i;
  }
  return [ix, ixx];
}

This returns the indexes of x and x^2 or, if not found -1 for the respective index. It returns, once both values are found in the list

Upvotes: 0

MrSmith42
MrSmith42

Reputation: 10161

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).

Upvotes: 0

Related Questions