Is my thought process for a big-o question correct?

Question

For this question:

Approximate the runtime of the following code fragment, in terms of n: Write you answers in a format such as O(N^2) or O(N log N):

int sum = 0;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= 1000000; j++) {

sum += 10;

}

}

sum+=9999;

Why is the answer O(N)? Is it because the first for-loop is O(N) and the second for-loop is O(1000000), which then gets reduced into O(1), so then since O(1) is so small, we only take O(N)? Is my thought process correct?

(Question is taken off of Practice-It from University of Washington)

Answer 1

Hello Lisa!

Your thought process is in the correct direction so I will just add some context to help you solidify your understanding. As you correctly noticed, the time complexity of the function (O(N)) is due to the inner loop being bound by a constant value. When we evaluate the time complexity of an algorithm and try to come up with a Big-O representation like O(N), we are really doing asymptotic analysis. That is, we are asking the question: "As the inputs (in this case the input is `n`) to the algorithm increase infinitely, how does the amount of "work" the algorithm has to do change?". In this case, as `n` gets larger and larger, the amount of steps the outer loop needs to perform grows proportionally to `n`. If `n` were to double, the number of steps performed by the outer loop would also double. If we were to graph this relationship it would be a straight line which is why the time complexity is linear or O(N). The work performed by the inner loop, however, is not tied to `n` and is the same even as `n` grows very large. This is why we can say that the time complexity of the inner loop is constant or O(1) and it is the number of steps the outer loop has to perform that dictates how the "work" this code has to perform increases as the input `n` gets increasingly large. This makes sense because any algorithm is only as efficient as the least-efficient part of it.