CODEWITHSUNDEEP
arraysbig-o
KeenLearnerA
KeenLearnerA

Reputation: 159

Determining efficiency (Big O Notation) while using arrays in JavaScript

I am struggling to wrap my head around Big O notation and saw the following problem online. I must answer determining whether the following code is O(n), O(n²), O(logn), O(nlogn)

I have watched several videos but am still failing to understand Big O. Can someone please advise to the answer and their methodology for getting there?

function sortSmallestToLargest(entries):
    sorted_entries = {};

    while entries is not empty:
        smallest_entry = entries[0]

        foreach entry in entries:
            if (entry < smallest_entry):
                smallest_entry = entry

        sorted_entries.add(smallest_entry)
        entries.remove(smallest_entry)

    return sorted_entries

Upvotes: 0

Views: 126

Answers (1)

BlackBrain
BlackBrain

Reputation: 1029

The algorithm iterates multiple time on 'entries' until it gets empty. first time in the inner loop it iterates n time (assuming entries length is n at start). second time in the inner loop it iterates n-1 time (because one item was removed in the previous iteration). So at the end we have this series of iterations:

n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n^2)

Upvotes: 2

Related Questions