1

What is the worst case running time of declaring a 2D array? The 2d array is not strictly square. I have seen answers that state it is O(n) and I have also seen answers that state its O(n²).

In my mind, when declaring an object array such as this:

Object[][] gridArray = new Object[i][j];

//The number of elements n = i*j

The time complexity when declaring the array should be O(n) as it will just scale linearly depending on how many elements there will be. Am I missing something?

Java Hermit
  • 21
  • 1
  • 3
  • Depends entirely on the language, which you didn't mention. Your code looks like Java. Allocating the memory in Java (under reasonable assumptions) takes constant time, but that's moot because setting all the values to `null` - which the language requires - requires O(i*j). C `malloc` and C++ default `new` will take constant time because they don't initialize the allocated space. – Gene Aug 21 '17 at 04:29
  • Note that *declaring* an array is an O(1) operation. It's *allocating* the array that can take variable time. – Jim Mischel Aug 22 '17 at 17:21

1 Answers1

2

It depends on what you mean by n.

Some may define n as your i and see the j depended to that, for example a square n * n, for that definition you get O(n^2), O(i * i) or O(i * j) if j in O(i).

However you defined it as n = i * j. So yes, it is O(n) for your definition of n but that notation hides O(i * j) which may be more appropriate.

However note that it depends on whether your language actually initializes all those array entries at creation. Some languages don't do that!

I guess your code is Java, this language actually sets every entry to an initial value. In your case this would be null, thus it indeed creates i * j elements and sets them to null, yielding O(i * j).

Also take a look at Syntax for creating a two-dimensional array, which explains in detail how your code works.

Zabuzard
  • 25,064
  • 8
  • 58
  • 82