Linear Data Structures

What if we have a print statement before and after our loop? What do you think is the runtime complexity of this method?

We know single operations running constant time. When we using the big O notation, we drop constants in this example because they don’t really matter. If our array has 1 million inputs, adding two extra operations doesn’t really have a significant impact on the cost of our algorithm. The cost of our algorithm still increases linearly, so we can simplify this by dropping this constant. What matters is that the cost of this algorithm increases linearly and in direct proportion to the size of our input. If you have five items in the input, we’re going to have five operations. If you have a million items, we’re going to have a million operations.

What if you had two loops here? What is the runtime complexity of method which had two loops?

This is another example where we drop the constant, because all we need here is an approximation of the cost of this algorithm relative to its input size. So, n or 2n still represents a linear gross.

Now what if this method had two parameters, an array of numbers and array of names? What do you think is the runtime complexity here?

Both these loops run in O(n). Here’s the tricky part. What is n in this case? We are not dealing with one input. We have two inputs, numbers and names. So, we need to distinguish between these two inputs. Suppose runtime complexity of the first input is O(n) and second input is O(m). So, the runtime complexity of this method is going to be O(n + m), and once again we can simplify this to O(n) because the runtime of this method increases linearly.

O(n²)
What is the runtime complexity when printing all combinations of items in an array using nested loops. In our outer loop, we’re iterating over our input array. So runtime complexity of outer loop is O(n) and in each iteration, once again you’re iterating over all the items in this array. Runtime complexity of inner loop is O(n). So, runtime complexity of this method is O(n^2).