(another) big O question

[unclepauly]

heres a question: i understand that array insertion is carried out in constant time - O(1) - but if the array is 2D (n*n), then would this still hold true if i wanted to insert the same value into each array?

let me explain a bit better, if i have a 2D array of ints, and the array looks like this:

1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

and i wanted to add a 6 onto the end of each array, plus an extra line (so the array size is still n*n) so it ended up looking like this:

1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6

then i would say that the insertion into the first line is achieved in constant (1) time - but there are n lines! so i think this is now 1*n =n. so is this linear? or is it still thought of as constant?

[Ravalon]

You're adding a constant number of items onto a variable number of lines. When you have a constant number of items, the big O is almost always going to be O(1) and when you have a variable number of items but you do a constant operation on every item, the big O is O(n). In that case, it's linear because you're always adding one number to every line. :)

[Rashakil Fol]

heres a question: i understand that array insertion is carried out in constant time - O(1) - but if the array is 2D (n*n), then would this still hold true if i wanted to insert the same value into each array?

Now what do you mean, saying array insertion is carried out in constant time? What do you mean by insertion? Exactly what datastructure are you using to represent the array? If you've got some naive array in memory somewhere, then you can't grow it at all, and you'll have to recopy the whole thing to a new location, and that takes O(n) operations! (Where n is the number of elements in the array.) But if you've got some space allocated on the sides of the array, you can shift array elements one unit over -- and in the worst case, that's still O(n) operations. If you mean to append an element to the very end of an array, that depends on whether you have pre-allocated extra space. If you have, it's O(1). If not, you'll need to reallocate and copy the entire contents over. Which is O(n). If you double your allocation space on each reallocation, you'll endure an O(1) cost per element added, on average, though. This form of array is called a vector, in C++.

let me explain a bit better, if i have a 2D array of ints, and the array looks like this:

1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

and i wanted to add a 6 onto the end of each array, plus an extra line (so the array size is still n*n) so it ended up looking like this:

1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6

This depends entirely on how you are implementing a 'multidimensional array'. Here's one possible implementation, given in C:

struct multidimArray {
  size_t num_rows, num_cols;
  int* data; /* pointer to a block of memory exactly num_rows*num_cols wide. */
};

Let's suppose that the data is structured in a way that groups rows together, so that the raw memory looks like 1 2 3 4 5 1 2 3 4 5... (instead of grouping columns, which would draw things like 1 1 1 1 1 2 2 2 2 2 ...).

Now to grow this multi-dimensional array, you'll need to reallocate the entire thing, which is an O(n^2) operation! (That's because there are n^2 elements that need to be copied -- remember that n refers to a specific value, which is not necessarily the size of your input.)

Now say your array has room to grow.

struct multiDimArray {
  size_t num_rows, num_cols;
  size_t space_allocated;
  int* data; /* pointer to a block that's at least num_rows*num_cols wide */
};

Now, on average, you can add new rows to the array, with small cost -- a cost equivalent to the size of the row. You could add a new row just by writing 2 3 4 5 6, starting at the num_rows*num_cols element in the data array. If you doubled the space allocated each time you had to reallocate, it wouldn't be much of a cost. So adding rows would be an O(n) operation (since each rows would contain n elements.) But adding columns requires a complete restructuring of the array! That would take O(n*m) operations, where n is the number of elements in a row and m is the number of elements in a column. (So m is the number of rows, n is the number of columns.) If you're starting off with an square array, that's O(n*n), of course, since n = m. Or O(n^2) if you like to write it that way.

But there are other ways of organizing multi-dimensional arrays. You don't need to have one contiguous chunk of memory; you can have separate contiguous chunks of memory for each row. Each row could be represented by a C++ vector (mentioned earlier), to which you can append elements with O(1) average cost. And you could have the entire matrix be represented by a vector of rows.

Something like

struc t {
  vector< vector<int> > matrix;
};

in C++. Then you can append 6's to each row, in constant time, which gives O(n) time since you've got to do it to n rows. You can append a new row to the vector of rows in 'constant time', which really means the amount of time it takes to copy a row onto the vector, which means you've got O(n+1) time there. (Remember that your new row has n+1 elements. Or your new column does. It's the same either way.) So then you've got O(2n+1) elements added, and since 2n+1 is a constant multiple of n, that's equivalent to O(n) operations.

So if you arrange your datastructures neatly, you can get away with fewer operations than if you arrange your datastructures less neatly. Which isn't to say that arranging your datastructures less neatly is a problem, if you're worried about memory efficiency or just don't see dynamically altering the size of matrices as something you'll want to do for your particular application.

There are a few other ways of arranging your datastructure that would have O(n) growth time instead of O(n^2), too, of course. Some of which work with contiguous blocks of memory. (For example, just make an array of the form array[n][n] and use the indices from 0 to n-1, which is fine as long as n is no more than 10. In C, this makes a contiguous block of memory. In other languages, this makes a solution more like the vector solution, with separate arrays for each row.)

[unclepauly]

awesome explanation - thanks to you both for your replies.