Like Tree2Likes
  • 1 Post By std10093
  • 1 Post By std10093

Filling 2D array complexity.

This is a discussion on Filling 2D array complexity. within the C Programming forums, part of the General Programming Boards category; Hello to all Assuming that we have : Code: int arr2d[rows][columns] ; // Not valid syntax of course ... let ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    293

    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?
    Last edited by Mr.Lnx; 03-24-2013 at 02:18 PM.

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    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 )
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  3. #3
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    293
    Quote Originally Posted by std10093 View Post
    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 )
    About invalid syntax ... I mean that I have no declare the variables rows and columns before. It is not some new or strange discovery :P

    Thank you for your answer

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    I thought you implied that this way of declaring a 2D array was incorrect.

    You are welcome

    PS - Χρόνια πολλά για την Εθνική μας εορτή!
    Last edited by std10093; 03-24-2013 at 04:29 PM.
    Mr.Lnx likes this.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  5. #5
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    293
    I Have some questions about complexity though. I have this source :

    Complexity and Big-O Notation

    Assuming the point :

    Code:
    for (i = 0; i < N; i++) {
        for (j = i+1; j < N; j++) {
            sequence of statements
        }
    }

    Code:
    Value of i Number of iterations of inner loop
    0 	          N
    1 	          N-1
    2 	          N-2
    ... 	         ...
    N-2 	         2
    N-1 	         1
    If N=5 i will have N-2 = 3 value so j will have i+1 = 4 but it will do 2 iterations in the inner loop..... we consider the actions which would be 4 < 5 TRUE and 5 < 5 FALSE?
    that is why the number of iterations of inner loop is 2?

    and the last one :

    Complexity of N * O(1) said to be O(N) this calculation based on algebric O(N*1) = O(N) or we say that is O(N) because we choose the worst case between two or many?

    P.S - Χρόνια μας πολλά !!!!!!!!!!!!!

  6. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    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..
    Last edited by std10093; 03-24-2013 at 06:22 PM.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  7. #7
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    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
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  8. #8
    Registered User
    Join Date
    Sep 2011
    Location
    Athens , Greece
    Posts
    293
    Quote Originally Posted by std10093 View Post
    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..
    Sorry for my english..... they need practice :P may you have answered in my question ..... but I am wondering since i has the value 0 and the inner loop starts from j=1 how can have N iterations??? Assuming that N is 3 so j=1 ..... j < 3; we have j=1 , j=2 iterations .... (2 not three (N) ) my question is that we must consider and the case that check 3 < 3 gives FALSE? Maybe is very simple as a question .... maybe is silly :P

    the 3 iterations of inner loop on this case is 1 < 3 (TRUE) ... 2 < 3 (TRUE) and 3 < 3 FALSE?

    Thank you in advance ....

    p.s Now I see your post above... just a minute !!!

  9. #9
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    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. Καληνύχτα.
    Mr.Lnx likes this.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 2D array filling
    By martynasj in forum C Programming
    Replies: 6
    Last Post: 11-16-2012, 03:14 PM
  2. Filling an array
    By DeanWinchester in forum C Programming
    Replies: 4
    Last Post: 09-07-2012, 12:30 AM
  3. array search complexity problem
    By vnbp8187 in forum C Programming
    Replies: 6
    Last Post: 02-24-2011, 11:45 AM
  4. Filling up a 2D (or 3D) array.
    By omnificient in forum C Programming
    Replies: 1
    Last Post: 01-20-2008, 12:22 PM
  5. Filling an array
    By nizbit in forum C Programming
    Replies: 3
    Last Post: 01-23-2005, 01:02 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21