Big O Notation: A Common Mistake and Documentation

Jessica YungProgrammingLeave a Comment

A Question

What’s the time complexity of the following algorithm? (Don’t know how to calculate that? Here’s a nice intro to Big-O Notation from InterviewCake.)

O(n^2)?  Nope.

If array_x has length x and array_y has length y, the algorithm has time complexity O(xy) since one loop with a constant number of operations is run y times for each iteration of a loop that is run x times.

I got this wrong the first time, and turns out it’s a very common mistake. So be careful!

Documentation

It is helpful to document the time and space complexity of an algorithm when you are writing it so you (and other readers) don’t have to recalculate it for themselves when they are using or considering it. It is also good practice (both ways). It is not always done but I find it helpful. A documented version of the above algorithm would then be:

 

It often helps to include an example, but for this simple algorithm it might be overkill (Would love to hear your opinion in the comments.):

 

(On a related note, I realised that WordPress’s pre tags don’t show code that well and will be looking into alternatives. Do tell if you have any recommendations.)

Bonus

Here’s a useful table of the time and space complexities of common algorithms from Big-O Cheat Sheet:

Source: Big-O Cheat Sheet by Eric Drowell. Disclaimer: I have not checked these.

 

Further reading:

Intro to Big O Notation from InterviewCake

Big-O Cheat Sheet by Eric Drowell (space and time Big-O complexities of common algorithms)

Python Style Guide PEP8

Leave a Reply