Time Complexity of im2row and im2col

In this article at OpenGenus, we have explored the time and space complexity of im2row and im2col algorithms that are frequently, used for GEMM based Convolution algorithms.

Time Complexity of im2row and im2col

In short:

• Time Complexity of im2row = Output Width x Kernel Height x Kernel Width x Number of Channels
• Time Complexity of im2col = Output Height x Kernel Height x Kernel Width x Number of Channels

im2row = OW x KH x KW x C
im2col = OH x KH x KW x C

Note the difference between im2row and im2col in terms of time complexity is the first parameter. im2row has Output Width (OW) whereas im2col has Output Height (OH).

Space Complexity of im2row and im2col

The space complexity of both im2row and im2col is O(Input Height x Input Width x Channels) provided im2row and im2col are not in-place algorithms.

If you do not want to consider the output patch matrix/ data, then space complexity of im2row and im2col is O(1).

im2row and im2col in Convolution

When im2row and im2col is called in Convolution, the function (im2row or im2col) is called B times where B is the batch size or the number of images to be processed.

Due to this, the time complexity for im2row or im2col function in Convolution becomes:

im2row = B x OW x KH x KW x C
im2col = B x OH x KH x KW x C

With this article at OpenGenus, you must have the complete idea of Time and Space Complexity of im2row and im2col.