what is the difference between O(nk) and O(n+k) in

问题:

In big O notation of time complexity in algorithmic analysis, when an algorithm depends on n and k, what is the difference between these two notations. Also pls help in the notation to use if there is a nested loop with outer loop running n times and inner loop running k times ?

回答1:

O(nk):

for( i=0; i<n; i++ ) {
   for( j=0; j<k; j++ )
   {}
}

O(n+k):

for( i=0; i<n; i++ )
{}

for( j=0; j<k; j++ )
{}

回答2:

O(n+k) indicates a linear growth rate in the larger of n or k. Suppose n is greater. Then

n + k <= n + n = 2n = O(n)

If n is smaller, though, then

n + k <= k + k = 2k = O(k).

Whether or not n is the larger, it's always true that

n + k = O(n+k)

so this notation helps hide that uncertainty. Such two-variable notation is useful for graph algorithms, using n for the number of vertices and m for the number of edges. You can write one expression, O(n + m), to indicate that the algorithm is O(n) for sparse graphs (m = Theta(n)) but slower for more dense graphs (e.g., O(n^2) if m = Theta(n^2)).

For the second question, it's just simple arithmetic. You iterate the inner loop k times on the first iteration of the outer loop, k times for the second, etc, for a total of k+k+...+k = n*k total operations, which is O(nk).

回答3:

O(nk) means the time it takes is proportional to n * k. O(n+k) means the time it takes is proportional to n + k. It's exactly what it seems like. You will need to be more specific in your question about what you don't understand.

In your case, the algorithm's runtime is O(nk) because the inner loop runs a total of n * k times.

回答4:

It should be clear that these are different since, for example if n=k:

O(nk)=O(nn)=O(n^2)

O(n+k)=O(2n)=O(n)

回答5:

Saying that function f(n) is O(g(n)) means that there exists some constant q such that for all values of n which are no less than one, f(n) will be no greater than q g(n).

Conversely, saying that function f(x,y) is O(g(x,y)) means that there exists some constant q such that for all values of x and y which are no less than one, f(x,y) will be no greater than q g(x,y).

If k is a constant, then both values above are equivalent to O(n) since for any value of k, and for any n which is no less than one, if one sets q equal to (k+1), then neither nk nor n+k will exceed qn [i.e. (k+1)n] for any value of n which is no less than one.

If k and n are both fully-independent variables, then O(nk) is irreducible; O(n+k) will be O(max(n,k)), since if one sets q equal to 2, q(max(n,k)) [i.e. 2max(n,k)] will be greater than or equal to n+k for all values of n and k which are no less than one.