Witty Timmy II

First, we notice that the output vector consists of $n^2$ entries, each of which is a dot product of two vectors of $n$ components.

Since computing the dot product of two vectors require summing over all $n$ corresponding pairs of components, this task is $O(n)$ .

Doing an $O(n)$ task $O(n^2)$ times takes time in $O(n^3)$

Actually, one can use Strassen's Algorithm for faster multiplication.

Here is the algorithm for multiplication of two square matrices of same order $r \times c$ with $r=c=n$

1
2
3
4
5

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]

The time complexity is $O(n^3)$ ..