3

I have a trouble in understanding time complexity. People can look at algorithms and directly say what its time complexity is, but I can't do that well.

Consider two n * n matrices (A and B). Their multiplication result is C. So, value of C11 consists of n multiplications and n-1 additions. How come that its time complexity is O(n^3)? I would say O(n^2).

Can someone explain it in understandable language? I know what's theta , I know what is big O, but I just can't implement this stuff.

And if you provide another simple example similar to above, that would be greatly appreciated.

Lerner Zhang
  • 6,184
  • 2
  • 49
  • 66
rakamakafo
  • 1,144
  • 5
  • 21
  • 44
  • In a very broad way, you have 2 `fors` to run through all the C cells that you need to calculate, and 1 `for` to do the calculations -> 3 `fors` -> `O(n³)` – Isac Oct 19 '17 at 01:26
  • 1st FOR: going through rows of A, 2nd FOR: through columns of B, and 3rd FOR adds, right? How would you understand it, on a fly? Or you have to write that algorithm quickly to see that complexity? – rakamakafo Oct 19 '17 at 01:33
  • 1
    Not really you have to visualize the code in order to be able to see its complexity. If you know it by heart than you can picture it in your head. Take a look at [this SO answer with a java matrix multiplication](https://stackoverflow.com/a/17624210/6087092) and see the 3 for loops – Isac Oct 19 '17 at 01:36

1 Answers1

4

Simply put, your matrix C has n x n cells, which requires n^2 operations for all cells. Calculating each cell alone (like c11) takes n operations. So that would take O(n^3) time complexity in total.

You said that computing a cell in C (like c11) takes n^2 is not really correct. What it takes to compute c11 is to loop from 1 to n (write it down on paper and you will see), which is O(n) time complexity.

Practice makes perfect. Just try more problems and you will be good at it. Also, Facebook has an interview preparation tool called codelab for you to improve those related stuff.

Hope this helps!

Khang Vu
  • 329
  • 4
  • 13
  • Can we say like this. Cell C11 requires n+(n-1) operations, which is O(n), and then calculating first raw of C is n*(2n-1) which is O(n2). And then calculating all rows of C takes n*n*(2n-1) which is O(n3). Is this correct? – rakamakafo Oct 19 '17 at 01:41
  • @Sher: your thinking sounds good, but I suggest you should not go too much into details why cell C11 takes 2n - 1 operations. It's good to know that, but it could make you confused calculating such an exact answer, specially when you have more loops to calculate. Also, in many cases, you cannot calculate that exact value if you don't assume it to be the best case or the worst case. For example, in linear search, we need to loop from 1 to n to find a value say k. If k is the first element, then it only takes 1 operation. But if k is the last element, it takes n operations. – Khang Vu Oct 19 '17 at 03:07
  • @Sher: Also, this can be helpful: https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it?answertab=votes#tab-top – Khang Vu Oct 19 '17 at 04:47