CODEWITHSUNDEEP
javascriptalgorithmtime-complexity
motioncity
motioncity

Reputation: 17

Is the time complexity of this function O(log n)?

I am trying to do this problem on LeetCode, and the following is the solution I came up with:

var findKthLargest = function(nums, k) {
  //var tmp = nums.slice();
  var iteration = 0;

  while (iteration < k) {
    var max = -Infinity;
    for (var i = 0; i < nums.length; i++) {
      var cut;
      if (nums[i] > max) {
        max = nums[i];
        cut = i;
      }
    }
    nums.splice(cut, 1);
    iteration++;
  }

  return max;
};

Now, I believe this is a log n solution because what I’m basically doing is removing the largest value in the array, which decreases my number of comparisons. However, it only beats 59% of the JavaScript solutions, which makes me think I might not have the right complexity.

Upvotes: 0

Views: 78

Answers (1)

Barmar
Barmar

Reputation: 780871

There are k iterations of the while() loop (which, I think, would be more idiomatically written as for(var j = 0; j < k; j++)).

The first iteration then performs n iterations of the for loop, and nums.splice(cut, 1) is O(n) because it has to shift all the array elements from cut to n. O(2n) is the same as O(n) because constant factors are ignored in big-O calculation.

The second iteration performs n-1 iterations. This is also O(n) because we ignore constant adjustments in big-O notation. The same goes for the splice.

So the final result is that it's O(k * n), since you have k iterations of the outer loop, and the inner loops are each O(n). The worst case, when k >= n, is O(n^2)

Upvotes: 2

Related Questions