Time Space Complexity of k smallest of unsorted array-CodePudding

I solved this problem given to me in an interview, but I do not know what the Time Space complexity is.

What is the Time Space complexity of the following solution?

// Ordered Map Method
function orderedMapFrequency(array) {
  const map = {};
  for (let i = 0; i < array.length; i  ) {
    if (!map[array[i]]) {
      map[array[i]] = 1;
    } else {
      map[array[i]]  ;
    }
  }
  return map;
}

function kSmallest(arr, k) {
  let map = orderedMapFrequency(arr);
  let frequencies = 0;
  for (const [key, val] of Object.entries(map)) {
    frequencies = frequencies   val;
    if (frequencies >= k) {
      return key;
    }
  }
}

// variables
let input;
let k;

input = [7, 10, 4, 3, 20, 15];
k = 3;
console.log(kSmallest(input, k)); // 7

input = [7, 10, 4, 3, 20, 15];
k = 4;
console.log(kSmallest(input, k)); // 10

input = [12, 3, 5, 7, 19];
k = 2;
console.log(kSmallest(input, k)); // 5

input = [7, 0, 25, 6, 16, 17, 0];
k = 3;
console.log(kSmallest(input, k)); // 6

I think it might be O(log(n)) or is it simple O(n)?

CodePudding user response：

Space Complexity

O(N)

Time Complexity

O(NlogN)

Insertion of an entry into an ordered map is O(logN), therefore to create such an ordered map from an array is O(NlogN). Your orderedMapFrequency is thus O(NlogN). Find the kth smallest element by iterating over the ordered map is O(k), which is dominated by the creation of the ordered map. Therefore the overall time complexity is O(NlogN).

Appendix

You can check here to find solutions with better time complexity.
It is interesting that the Object {} in Javascript acts as an ordered map for integer keys, see Does ES6 introduce a well-defined order of enumeration for object properties? :

Integer indices (if applicable), in ascending order.

CodePudding user response：

Your solution uses a characteristic of JavaScript objects: keys that are decimal representations of indexes will be iterated in sorted order when calling functions like Object.entries.

From the specification we can only learn that setting and getting object properties must have sub-linear time complexity (see Javascript ES6 computational/time complexity of collections), so it is not an absolute requirement of the language that these operations run in constant time.

If these were constant in time, and iteration over these properties would take linear time, then we would have found a method to sort numbers in linear time, which is not possible unless some restrictions apply which would allow for a non-comparative sorting algorithm such as radix sorting algorithms.

And there are restrictions here: object keys are only iterated in their numerical order when these numbers are integers in the range 0 to 2³¹-1. So this does not apply for:

negative values
fractional numbers
numbers greater than 2³¹-1 (See also Object.keys order for large numerical indexes?)

Such keys will be iterated after other numbers, in the order they were inserted (which is what also happens with keys that are not numeric representations at all). So your solution can produce wrong results when such cases occur.

Here is a run of your code on slightly adapted inputs that violate one of the above conditions:

let input, k;

input = [7, 10, 4, -3, 20, 15]; // Notice -3
console.log(kSmallest(input, 3)); // 10 (should be 7)

input = [7, 10, 4, 3.1, 20, 15]; // Notice 3.1
console.log(kSmallest(input, 4)); // 15 (should be 10)

input = [12000000000, 3000000000, 5000000000, 7000000000, 19000000000]; // Big numbers
console.log(kSmallest(input, 2)); // 12000000000 (should be 5000000000)

// Your functions (unchanged)
function orderedMapFrequency(array) {
  const map = {};
  for (let i = 0; i < array.length; i  ) {
    if (!map[array[i]]) {
      map[array[i]] = 1;
    } else {
      map[array[i]]  ;
    }
  }
  return map;
}

function kSmallest(arr, k) {
  let map = orderedMapFrequency(arr);
  let frequencies = 0;
  for (const [key, val] of Object.entries(map)) {
    frequencies = frequencies   val;
    if (frequencies >= k) {
      return key;
    }
  }
}

As you can see, the outputs are not the k-smallest that you would have expected.

If the aim is for the algorithm to work also in those cases, then you can no longer rely on this specific behaviour of JavaScript objects and the property iteration order of functions like Object.entries, and you'll have to come up with an explicitly written algorithm (like for example using a heap data structure), which will have O(nlogk) time complexity if well done.

As to the time complexity of your algorithm: it depends on the JavaScript engine, but it seems many do a good job in providing near constant time complexity for the get/set operations on object key collections. So that would mean your solution provides a O(n) time complexity in practice. But:

A JavaScript implementation is allowed to provide O(logn) time complexity for get/set operations on object key collections, so then your solution has a O(nlogn) time complexity.
The above-mentioned restrictions make any statement about time complexity less meaningful.

The space complexity is trivial: O(n).