MVernik's blog

By MVernik, history, 4 years ago, In English

Confused...


Back-end part: int[][] matrix = new int[n][m]; int[] array = new int[n*m]; traversMatrix(matrix); traversArray(array); Client part: function traversMatrix(matrix : int[][]) for (i..n) for (j..m) doActions(); function traversArray(array : int[]) for (i..array.size()) doActions(); =================================== Time Complexity for traversMatrix: Quadratic Time Complexity for traversArray : Linear? Why?
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

"Quadratic" and "linear" are oversimplified, to tell the full story you have to say "quadratic in $$$x$$$" where $$$x$$$ is some variable.

For example, $$$t = 2^n$$$ is exponential in $$$n$$$, but it's actually sublinear in $$$4^n$$$. (If you substitute $$$m = 4^n$$$, you get $$$t = \sqrt{m}$$$.)

So your first method is quadratic in $$$n$$$ and $$$m$$$ (it's $$$t = n \times m$$$). Your second method is linear in $$$s$$$ (if you let $$$s$$$ be the length of the array), since it's $$$t = s$$$, but $$$s = n \times m$$$ so this is just $$$t = n \times m$$$ again. They take the same runtime.