1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.