Difficulties formulating a square matrix algorithm in O(n) time

user_13710987 0
Viewed 136

I am looking back on some past papers, for my exam, and I have come across a square matrix algorithm question/analysis that I cannot for the life of me approach.

Basically, I am given a N by N matrix (a square matrix basically), and I need to implement a data structure that allows me to increase the size of the matrix by 1 (row + 1, column + 1) in O(n) time.

After coercing my tutor, I realise the best data structure would be an array of arrays, so so essentially an something like this [ {1,2,3},{4,5,6},{7,8,9} ] this would denote my matrix, row 1, row 2, row 3

Now I need to be able to expand this matrix by 1 when the increase_size() method is called, I have already tried a naive solution, that is create a new empty array of size 4 sinze our previous matrix has 3 elements, append this array to our matrix_array, and then add a 0 to all the remaining arrays, however this takes O(n^2) time.

I believe there is something here that is related to the rows and columns, when we increase our matrix size we are essentially creating a new row and column, I believe this has something to do with the solution.

I have attached the question below.

enter image description here

big-o matrix time optimization algorithm
2 Answers

Try an array of arrays:

M = [ A1, A2, ..., An ]

each array Ax contains the values a_{i,j} if max(i,j) == x.

I'll let you do the proofs.

user_116412780

naive solution works in O(n) actually:

  1. consider any matrix of size n * n implemented as array of arrays (where arrays are dynamic)
  2. to reach size n + 1 we first create a new array of size n and append to the end of our matrix, this takes O(n) time
  3. then for every row in our matrix we append a 0 to the end we have n + 1 rows and append 1 element each so this too takes O(n) time
  4. in total runtime is O(n)
user_40591450
Related