Big-O insert for 2 dimensional array

Question

If i have N x N 2 dimensional array and the name is a.

int a[N][N];

When i Insert any value in any array, for example, a[N-1][N-1]=1, how much time does it take?

O(N^2) or O(1)?

Answer 1

You are not inserting, right? You are assigning, direct to a specific address and you don't need to figure out the right position before hand.

That means you don't need to do any loop, don't need to go through any computing before find the position and assign, and the memory is already allocated.

so it's O(1), constant doesn't matter the input.

Answer 2

Since you are assigning value directly to a particular position in an array so that ORDER will be O(1)

if you are iterating over it via 2 loops then it will be O(n^2) since for each i there will be a complete j iteration. For example:

for(int i=0; i<n;i++){
 for(int j=0; j<n;j++){
 }
}

Answer 3

1. I suppose you are talking about ordered array, because for unordered it is O(1). You copy element [n][m] to the end and put new element to [n][m]
2. I think you are talking about inserting, and not assigning, because for assign it is O(1).
3. if your array is ordered then O(N*N) to move all elements

Answer 4

an assignment operation in c can be threated as a O(1) for primitives

however: if you are doing a lot of assignments for random positions other players come out to the field...

consider the following 2 examples:

ex1.c:

#define W 1<<12
#define H W
int a[H][W];

int main(){

    for(int j=0;j< W ;j++){
    for(int i=0;i< H ;i++){
       a[i][j]=1;
    }
    }
    return 0;
}

ex2.cpp:

#define W 1<<12
#define H W
int     a[H][W];

int main(){

    for(int j=0;j< H ;j++){
    for(int i=0;i< W ;i++){
       a[i][j]=1;
    }
    }
        return 0;
}

CFLAGS=-O3 g++ ex1.c -o e1  && g++ ex2.c -o e2  && time ./e1 && time ./e2 && time ./e1
user    0m0.332s
user    0m0.048s
user    0m0.320s

as you can see ex1 was slower!

dependending on the used compiler optimazation level and it's abilities these two can behave very differently, even thru they are doing the same

if you are doing some random access, the cpu L1 cache will start to miss pages, which will cause a few wasted cycles to pull/put a page. if L2 was able to service L1's miss, then that's okay - if L2 has a miss the same happens at the L2 level...i think you get the picture ;)

more: http://en.wikipedia.org/wiki/CPU_cache

you may even create data hazards, it's impact is a magnitude smaller - but very intresting http://en.wikipedia.org/wiki/Hazard_%28computer_architecture%29#Data_hazards