# Time complexity of GPU computing

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)$$

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)$$.

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".

• 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 Commented Sep 24, 2023 at 16:38

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

• "asymptotics" !
– user16034
Commented Sep 17, 2023 at 10:22