runtime complexity
hello !
i would like have help in the calculation of runtime complexity.
Matrix .
given matrix which its columns are sorted in an ascending order , and also its rows ascending in an ascending order .
the demand is to print all the matrix members in an ascending order .
the naive solution for that would be :
pseudocode :
1.while there are members in the matrix:
a. find the minimum in the matrix and print it , than delete it .
what is the runtime complexity for that ?
thank you all for helping .
nice day !
i would like have help in the calculation of runtime complexity.
Matrix .
given matrix which its columns are sorted in an ascending order , and also its rows ascending in an ascending order .
the demand is to print all the matrix members in an ascending order .
the naive solution for that would be :
pseudocode :
1.while there are members in the matrix:
a. find the minimum in the matrix and print it , than delete it .
what is the runtime complexity for that ?
thank you all for helping .
nice day !
Last edited on
| find the minimum in the matrix and print it , than delete it. |
And why do you need to delete items if all you're doing is printing values from it?
It appears to be O(N) where N is # of rows*cols. Its sorted, so find the min is O(1) each iteration (its the next item in the loop through). Deletion is O(1) presumably (why do this??). Its just a 1 time traversal of the data, which is O(n). If it were not sorted, it would be another story, and it would depend on how it is stored what you can do with it there.
are you asking what it is if you start from the beginning over and over and skip deleted items? That's a different answer, but you would not DO that.
are you asking what it is if you start from the beginning over and over and skip deleted items? That's a different answer, but you would not DO that.
Last edited on
Topic archived. No new replies allowed.