MVernik's blog

Time complexity
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.

→ Reply