1
$\begingroup$

The time complexity of the matrix product is $O(n^3)$ if calculated normally for each element.

If computed on GPU, is it $O(n)$?

What I thought:

  • GPU can compute each element of the matrix product in parallel.
  • Each element is computed by a inner product of vectors $\sum_{k=1}^n a_kb_k$
  • Each $a_kb_k$ can be calculated in parallel, but the sum takes $O(n)$
Improve this question
$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

If you assume $n^2$ processing elements (which is unbounded), then yes the complexity is $O(n)$. But the total cost (complexity times number of PEs) remains $O(n^3)$.

On the opposite, if the number of PEs is bounded, the complexity remains $O\left(\dfrac{n^3}{p}\right)$, which is $O(n^3)$.

Improve this answer
$\endgroup$
0
$\begingroup$

From wikipedia

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm

It doesn't take into consideration the computing capabilities of the underlying machine. No matter the machine on which it is computed, the number of operations remain the same.

What you are looking after, would more suitably be called as order of "running time" or "execution time".

Improve this answer
$\endgroup$
1
  • $\begingroup$ this isn't true. assymtotics absolutely depend on machine. turing machines without random access memory will often have an extra factor of n attached to their complexity $\endgroup$
    – Oscar Smith
    Commented Sep 24, 2023 at 16:38
0
$\begingroup$

it's still O(n^3), big o notation is about asymptotics.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ "asymptotics" ! $\endgroup$
    – user16034
    Commented Sep 17, 2023 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.