it is O(nm)
I don't think your initial math is correct though
because you have (n+1)(m+1)
but after you expand this you will get something like m*n+m+n+1
and since m*n is the highest order here you will get O(m*n)
Pergunta
I have this question for my exam, and I could not figure it out: calculate the Big O for the following:
1)
for i = 0 to n // n - 0 + 2 = (n+2)
for j = 0 to m // m - 0 + 2 = (m+2)
x = x + 1
so does the answer become (n+2)(m+2) with O(nm) as the bigO?
Nenhuma solução correta
Outras dicas
it is O(nm)
I don't think your initial math is correct though
because you have (n+1)(m+1)
but after you expand this you will get something like m*n+m+n+1
and since m*n is the highest order here you will get O(m*n)
so does the answer become (n+2)(m+2) with O(nm) as the bigO?
Why n+2? It would be n+1 if 0 to n contains n, or it would be n, if n is exclusive. Therefore run time would me (n+1)(m+1) or (nm).
However, O(nm) would be in all cases.
yes.
You have 2 loops. So you have O(outer * inner). The outer loop is executed about n
times. The inner loop is executed bout m
times.
So O(nm) is appropriate.