Clever Geek Handbook

What is the difference between O (nk) and O (n + k) in time complexity?

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

+3


source to share


5 answers


About (pc):

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++ )
{}
+12


source


O (n + k) indicates linear growth rate at greater n or k. Let n be greater. Then

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

If n is less then

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


Regardless of whether n is greater than it is always true that

n + k = O(n+k)

so that this notation helps hide this ambiguity. This two-digit notation is useful for graph algorithms, using n for the number of vertices and m for the number of edges. You can write a single O (n + m) expression to indicate that the algorithm is O (n) for sparse graphs (m = Theta (n)), but slower for tighter graphs (e.g. O (n ^ 2) if m = Theta (n ^ 2)).

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

+1


source


O (nk) means the time it takes is proportional n * k

. O (n + k) means the time it takes is proportional n + k

. This is exactly what it seems. You need to be more specific about what you don't understand.

In your case, the execution time of the algorithm is O (nk), since the inner loop executes a total of n * k

times.

0


source


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

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

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

-1


source


Saying that the function f (n) is equal to O (g (n)) means that there is some constant q such that for all values ​​of n that are not less than one, f (n) will not be greater than qg (n).

Conversely, saying that the function f (x, y) is equal to O (g (x, y)) means that there is some constant q such that for all values ​​of x and y that are not less than one, f (x, y ) will be at most qg (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 that is not less than one, if we put q equal to (k + 1), then neither nk nor n + k do not exceed qn [ie (k + 1) n] for any value of n that is not less than one.

If k and n are completely independent variables, then O (nk) is irreducible; O (n + k) will be O (max (n, k)), because if we put q equal to 2, q (max (n, k)) [ie 2max (n, k)] will be greater than or equal to n + k for all values ​​of n and k that are not less than one.

-1


source






More articles:


All Articles