CODEWITHSUNDEEP
javascripttime-complexity
motioncity
motioncity

Reputation: 17

Is the time complexity of this function I found online O(n)?

I am trying to do this problem on LeetCode, and the following is the solution I found online:

//  use quick select
var findKthLargest = function(nums, k) {
    var smaller = [];
    var larger = [];
    var pivot = nums[parseInt(nums.length/2)];
    var pivotCnt = 0;

    for (var i = 0; i < nums.length; i++) {
        var num = nums[i];      
  
        if(num > pivot) {
            larger.push(num);
        }
        else if(num < pivot) {
            smaller.push(num);
        }
        else {
            pivotCnt++;
        }
    }
  
    if (k <= larger.length) { // if larger includes k
        return findKthLargest(larger, k);
    }
    else if (k - larger.length - pivotCnt <= 0) { // k is part of pivot
        return pivot;
    }
    else { // if smaller inclues k
        return findKthLargest(smaller, k - larger.length - pivotCnt);
    }
};

Now I believe this is an O(n) solution, because worst case is that we iterate through the entire array, but I'm not certain.

Upvotes: 0

Views: 47

Answers (1)

Tim Biegeleisen
Tim Biegeleisen

Reputation: 521073

Your function appears to be using some sort of divide and conquer approach. For each call, it makes a single O(n) pass over the input array, bucketing values larger than, and smaller than, a certain pivot, into two separate arrays. Then, it makes a recursive call on the appropriate subarray. In an average case, it will divide the size of the input array by two, until a recursive call is made on just an array of size one, which is the base case.

I would estimate that the running time of this function is O(n*lgn), which is typical for a divide and conquer algorithms. Each call does O(n) work, and there would typically be O(lgn) number of recursive calls.

Upvotes: 1

Related Questions