CODEWITHSUNDEEP
javascriptalgorithmbig-o
samgon
samgon

Reputation: 109

Finding time complexity of a simple function

I am trying to wrap my head around Big O. I have written two versions of a function that finds the "majority element" in an array (i.e. the element that occurs more than n/2 times where n is the length of the array). For example, if the input array is [2,2,1,1,1,2,2], the result is 2. My questions are:

  1. Is version 1 worst-case O(n^2)? [I think it is because countInstances is probably O(n) and the main function might end up calling it n times]
  2. Is version 2 O(n)? [This probably has something to do with using Map, but I'm not 100% clear about that]

Any clarification would be highly appreciated!

Version 1

function countInstances(arr, instance) {
    return arr.filter((el)=>el===instance).length
}


function MajorityElement(arr){
    let uniques = new Set(arr)
    let threshold = Math.floor(arr.length/2)
    for (el of uniques){
        if (countInstances(arr, el)>threshold){
            return el
        }
    }
    return null
}

Version 2

function getFrequencies(arr){
    let freqs = new Map
    for (el of arr){
        if (freqs.has(el)){
            freqs.set(el, freqs.get(el)+1)
        } else{
            freqs.set(el,1)
        }   
    }
    return freqs
}

function majorityElement(arr){
    let freqMap = getFrequencies(arr)
    let n = Math.floor(arr.length/2)
    
    for (let key of freqMap.keys()) {
        if (freqMap.get(key)>n){
            return key
        }
    }
    return null

}

Upvotes: 0

Views: 80

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 370699

You're right. .filter will always iterate over every element of an array, so if the callback is O(1) (which it is in this case), the .filter operation is O(n). countInstances is O(n).

You call countInstances inside a loop:

for (el of uniques){
    if (countInstances(arr, el)>threshold){

adding another dimension, so you get O(n ^ 2).

In the second code, there are no nested loops. The only loops are:

function getFrequencies(arr){
    let freqs = new Map
    for (el of arr){
        // linear operations

and

for (let key of freqMap.keys()) {
    // linear operations

so it's O(n).

Upvotes: 1

Related Questions