We often use Big O notation to reason about algorithm efficiency.
But here's something interesting: Two implementations of the exact same O(n³) algorithm can have drastically different execution times.
The reason? Memory access patterns.
Let's look at matrix multiplication.
The two implementations
Both implementations perform the same matrix multiplication:
[
C[i][j] += A[i][k] \times B[k][j]
]
They perform the same asymptotic amount of work. The only difference is the order of the loops.
Column-wise access
// Walk down columns of B for ( int i = 0 ; i < n ; ++ i ) for ( int j = 0 ; j < n ; ++ j ) for ( int k = 0 ; k < n ; ++ k ) C [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ];
Enter fullscreen mode
Exit fullscreen mode
Notice B[k][j].
As k increments, we move down a column of B.
In C++, 2D arrays are typically stored in row-major order.…