Run Time of Nested Loop

Question

In the following loop

for i = 1 to n 
    doSomething O(1)
    for j = 1 to k
        doSomething O(1)

Is the runtime still $O(nk)$ even with the expression in the outer loop? Because if I change the order of the loops and $n \neq k$ then doSomething is executed a different amount of times.

Answer 1

The running time is $O(n+nk) = O(nk)$, where we are making the implicit assumption that $n,k \geq 1$. This is usually a reasonable assumption.

If we do allow $n$ and $k$ to be zero then the running time becomes $O(nk + n + 1)$.

Let me comment that there are several different definitions of big O, which are usually but not always equivalent. Here I am using the following definition: $f(x_1,\ldots,x_m) = O(g(x_1,\ldots,x_m))$ if there exists a constant $C>0$ such that for all integers $x_1,\ldots,x_m \geq 0$, it holds that $0 \leq f(x_1,\ldots,x_m) \leq C g(x_1,\ldots,x_m)$.