Spencer Davis
Nov 4 · 1 min read

Great article describing bubblesort. I do think it is important to also give the space time complexity which goes hand in hand with algorithms especially if it is a test question.

So we need to refer to Big O notation. For time complexity:

This is a calculator program I found from https://www.desmos.com/calculator

I put in the equations. The y axis is time to run the program

y = x, this represents the red line which is O(n) which means linear time

y = x², this is the black line. Takes longest with big datasets. O(n²)

y = x log x, this is green line. better than one O(n²). O(nlogn)

y = log x , this is purple line. best performance

Usually the Quicksort or Mergesort falls somewhere around the green line but since it is recursive it requires some space memory for the call stack or if you create a separate stack which is the same.

Since this is bubblesort is somewhat brute force, it is a loop within a loop so average and worst case complexity is O(n²) while best case is O(n) meaning it is pretty much sorted already. The space complexity is 1.

Just thought it was worth adding.

    Spencer Davis

    Written by

    Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
    Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
    Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade