##### 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.)

1 2 3 4 5 6 7 |
def all_interarray_pairs(array_x, array_y): for i in range(len(array_x)): for j in range(len(array_y)): print(array_x[i],array_y[j]) |

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.

1 2 3 4 5 6 7 8 |
def all_interarray_pairs(array_x, array_y): # This loop is run x times for i in range(len(array_x)): # This loop is run y times for j in range(len(array_y)): # This is a constant number of operations print(array_x[i],array_y[j]) |

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def all_interarray_pairs(array_x, array_y): """ <em>Prints all inter-array pairs (one element from array_x, one from array_y). Time complexity: O(xy), where x = len(array_x), y = len(array_y) Space complexity: O(1) </em> """ for i in range(len(array_x)): for j in range(len(array_y)): print(array_x[i],array_y[j]) |

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.):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
def all_interarray_pairs(array_x, array_y): """ <em>Prints all inter-array pairs (one element from array_x, one from array_y). Time complexity: O(xy), where x = len(array_x), y = len(array_y) Space complexity: O(1)</em> <em> >>> all_interarray_pairs([1,2],[3,4])</em> <em> [1,3],[1,4],[2,3],[2,4] </em> """ for i in range(len(array_x)): for j in range(len(array_y)): print(array_x[i],array_y[j]) |

(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:

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)