Geek Answers Handbook

What is the time complexity of the code?

Is the time complexity of the following code O (NV ^ 2)?

for i from 1 to N:
    for j from 1 to V:
        for k from 1 to A[i]://max(A) = V
           z = z + k
+4
source share
2 answers

Yes, whenever we talk about O-notation, we always think about the upper bound (OR in the worst case) .

Thus, the complexity of this code will be equal to

O(N*V*maximum_value_of_A)
=O(N*V*V)   // since,maximum value of A=V,so third loop can maximally iterate from 1 to V---V times
=O(N*V^2).
+2
source

Of course, this is O (NV ^ 2), because it means that the code will never be slower than that. Since max (A) = V, you can say that the worst case is when each index A has V. If so, then the complexity can be limited to O (NV * V).

, for k O (avg (A)). , Omega (NV * avg (A)), avg (A) <= V.

- ( ) Theta (NV * O (V)), O (V), , , V, .

+1

More articles:


All Articles