CODEWITHSUNDEEP
arraysalgorithmbig-otime-complexity
Layla
Layla

Reputation: 5446

Algorithm complexity in 2D arrays

Let's suppose that I have an array M of n*m elements, so if I want to print its elements I can do something like:

for i=1 to m
    for j=1 to n
       print m[i,j]
    next j
next i

I know that the print instruction is done in constant time, so in this case I would have an algorithm complexity of:

\sum_{i=1}^{m}\sum_{j=1}^{n}c=m.n.c

so I suppose is in the order of O(n)

But what happens if the array has the same number of rows and columns, I suppose the complexity is:

\sum_{i=1}^{n}\sum_{j=1}^{n}c=n.n.c

so it is of order O(n^{2})

are my assumptions correct?

Upvotes: 0

Views: 1102

Answers (1)

templatetypedef
templatetypedef

Reputation: 372754

I'm assuming that m and n are variables and not constants. In that case, the runtime of the algorithm should be O(mn), not O(n), since the runtime is directly proportional to the number of elements in the array. You derived this with a summation, but it might be easier to see by just looking at how much work is done per array element. Given this, you're correct that if m = n, the runtime is quadratic on n.

Hope this helps!

Upvotes: 4

Related Questions