Algorithm complexity in 2D arrays

Question

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?

The first one should be O(m*n), I think. There's no real limit to the number of variables that can be used to represent complexity of an algorithm; It's just not seen quite as often as using 'n' alone. — Serge
– Serge, Commented Aug 26, 2014 at 18:10

templatetypedef · Accepted Answer · 2014-08-26 18:10:36Z

4

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!

answered Aug 26, 2014 at 18:10

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Algorithm complexity in 2D arrays

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related