Thread: Filling 2D array complexity.

Hello to all

Assuming that we have :

Code:

int arr2d[rows][columns] ;  // Not valid syntax of course ... let be arr2d rows * columns size

for(int i=0; i<rows; i++)
for(int j=0; j<columns; j++)
arr2d[rows][columns] = some_value;

What is the complexity? I believe O(n) and not O(n^2) on this case because if you have 3*3 size you would put 9 elements (from 9 elements input of course)... for each input you have one insertion and that is the meaning. Same as 4*4 size 16 input times 16 insertions .. or 5*5 and so forth....

Do you agree?

Well, this goes out of bounds. But let's say we have i and j (the complexity won't change). When I say complexity, I mean time complexity.

The complexity will be Ο(n²).
Τhe explanation is as you said.. For a 3x3 you would do the assignment 9 times, that is 3² and not 3.
Same for 4x4.

Tip: The complexity of a loop is the multiplying of the times each loop is going to be added.

In your case, that is rows*columns.

What do you mean not valid syntax (of course <- you seem pretty sure about it :P :P )

I thought you implied that this way of declaring a 2D array was incorrect.

You are welcome

PS - Χρόνια πολλά για την Εθνική μας εορτή!

The second one is true because of linearity...

The first one:

j will take the value of i+1... As a result, it will start from value 1, when you meet the inner loop for first time... Then, when you go to the inner loop for the 2nd time, it will have the value 2..
Thus, the sequence of statements is going to be executed N*(N/2) = N²/2 pretty much... it should be something less than that actually, but when N goes to really big numbers, like numbers that real applications use, you do not care for 100 or 200 times a sequence of statement is going to be executed..

In order to compute it accurately, you should do this:
Σ[base:i=0, upperBound:i=N-1] Σ[base:j = i+1, upperBound:j = N-1] 1

In order to get on with more complex calculations, you need to have taken a course in Discrete Mathematics (Διακριτά Μαθηματικά).

However, when talking about complexities, in order to conclude somewhere, you need to let n go to infinity..

Let's solve it
Σ[base:i=0, upperBound:i=N-1] Σ[base:j = i+1, upperBound:j = N-1] 1

= Σ[base:i=0, upperBound:i=N-1] (N - 1 - i - 1 + 1) 1

= Σ[base:i=0, upperBound:i=N-1] ( N - 1 - i )

= Σ[base:i=0, upperBound:i=N-1] N - Σ[base:i=0, upperBound:i=N-1] 1 - Σ[base:i=0, upperBound:i=N-1] i

= (N - 1 - 0 + 1)N - (N - 1 - 0 + 1) - [(N-1)( (N-1) + 1 )/2]

= N² - N - (N-1)N/2

= N² - N - (N² - Ν)/2

= N² - Ν - Ν²/2 + Ν/2

= (2Ν²-Ν²)/2 + (Ν - 2Ν)/2

= Ν²/2 + (-Ν)/2

= Ν²/2 - Ν/2

But, as N grows, N²/2 is going way above than N/2, thus, we keep only N²/2

However, I claim, that even though the loop will finish when i or j reaches N-1, we could use N as upper bounds in our sums, in order to get the same result.
Σ[base:i=0, upperBound:i=N] Σ[base:j = i+1, upperBound:j = N] 1

= Σ[base:i=0, upperBound:i=N] (N - i - 1 + 1) 1

= Σ[base:i=0, upperBound:i=N] (N -i)

= Σ[base:i=0, upperBound:i=N]N - Σ[base:i=0, upperBound:i=N] i

= (N - 0 + 1)N - N(N+1)/2

= N² + Ν - Ν²/2 + Ν/2

= (2Ν² - Ν²)/2 + (2Ν + Ν)/2

= Ν²/2 + 3Ν/2

but again N²/2 goes way above the 3Ν/2, as N goes to infinity, so we conclude that N²/2 is the answer.

Two tips:

• Σ[base:i = 0, upperBound:N] i = N(N+1)/2
• Σ[base:i = 0, upperBound:N] 1 = (N - 0 + 1) * 1

The second one can be reclaimed easily...
Let N = 3

Σ[base:i = 1, upperBound:3] 1 = 1 + 1 + 1 = 3
and
(3 - 1 + 1)*1 = 3*1 = 3

Hope this helps

We don't count the moment that the condition of the loop fails, since the sequence of statements is not going to be executed at all

As for the English, make sure you keep up with this forum... It really helps you practice your English and more importantly, to learn how the people in our science talk

Time for eat and sleep. Καληνύχτα.