Answers.Body: <h2>What is the time complexity?</h2>
  <p>The time complexity of an algorithm is the number of basic operations, such as multiplications and summations, that the algorithm performs. The time complexity is usually expressed as a function of the input's size <span class="math-container">$n$</span> (but this does not always have to be the case: for instance, you can express the time complexity as a function of the output's size).</p>
  <h2>Example</h2>
  <p>Rather than giving you a full answer to your question, I will try to help you by explaining, with the simplest example, how you should calculate the time complexity.</p>
  <p>For simplicity, let's assume that we have a kernel <span class="math-container">$\mathbf{H} \in \mathbb{R}^{3 \times 3}$</span> and input image <span class="math-container">$\mathbf{I} \in \mathbb{R}^{3 \times 3}$</span> (i.e. the kernel has the same dimensions as the input), we use a stride of <span class="math-container">$1$</span> and no padding. If we convolve <span class="math-container">$\mathbf{I}$</span> with <span class="math-container">$\mathbf{H}$</span>, how many operations will we perform? The convolution is defined as a scalar product, so it is composed of multiplications and summations, so we need to count both of them. We have <span class="math-container">$9$</span> multiplications and <span class="math-container">$8$</span> summations, for a total of <span class="math-container">$17$</span> operations.</p>
  <p><span class="math-container">\begin{align}
  \mathbf{I} \circledast \mathbf{H} 
  &amp;=
  \begin{bmatrix}
  i_{11} &amp; i_{12} &amp; i_{13} \\
  i_{21} &amp; i_{22} &amp; i_{23} \\
  i_{31} &amp; i_{32} &amp; i_{33}
  \end{bmatrix}
  \odot
  \begin{bmatrix}
  h_{11} &amp; h_{12} &amp; h_{13} \\
  h_{21} &amp; h_{22} &amp; h_{23} \\
  h_{31} &amp; h_{32} &amp; h_{33}
  \end{bmatrix}\\
  &amp;=
  \sum_{ij}
  \begin{bmatrix}
  i_{11} h_{11} &amp; i_{12} h_{12} &amp; i_{13} h_{13} \\
  i_{21} h_{21} &amp; i_{22}  h_{22} &amp; i_{23} h_{23} \\
  i_{31} h_{31} &amp; i_{32} h_{32} &amp; i_{33} h_{33}
  \end{bmatrix}\\
  &amp;=
  i_{11} h_{11} + i_{12} h_{12} + i_{13} h_{13} + 
  i_{21} h_{21} + i_{22}  h_{22} + i_{23} h_{23} + 
  i_{31} h_{31} + i_{32} h_{32} + i_{33} h_{33}
  \end{align}</span></p>
  <h3>Time complexity</h3>
  <p>What is the time complexity of this convolution? To answer this question, you first need to know the input's size, <span class="math-container">$n$</span>. The input contains <span class="math-container">$9$</span> elements, so its size is <span class="math-container">$n = 9$</span>. How many operations did we perform with respect to the input's size? We performed <span class="math-container">$17$</span> operations, so the time complexity <span class="math-container">$\mathcal{O}(2*n) = \mathcal{O}(n)$</span>, i.e. this operation is linear. If you are not familiar with the <a href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noreferrer">big-O notation</a>, I suggest that you get familiar with it, otherwise, you will not understand anything about computational complexity.</p>
  <p>To calculate the time complexity in the case the input's dimensions are different than the kernel's dimensions, you will need to calculate the number of times you slide the kernel over the input. You can't ignore this (as I ignored the constant <span class="math-container">$2$</span> above) because the number of times you slide the kernel over the input depends on the input's size, so it's a function of the input. Anyway, the paper <a href="https://arxiv.org/pdf/1603.07285.pdf" rel="noreferrer">A guide to convolution arithmetic for deep learning</a> contains a lot of information about convolution arithmetic, so it will be helpful.</p>
  <h3>Non-linearities, pooling and fully connected layers</h3>
  <p>Note that, in the above example, I ignored the non-linearities and pooling layer. You can easily extend my reasoning to include these operations too. I also ignored the operations in the final fully connected layers. You can find how to calculate the number of operations in an MLP <a href="https://ai.stackexchange.com/a/13626/2444">in this answer</a>. If you also perform other operations or have other layers other than convolutional, pooling and fully connected, of course, you will also need to take them into account.</p>
  <h3>Forward pass</h3>
  <p>Moreover, the time complexity of the forward pass of a CNN depends on all these operations in these different layers, so you need to compute the number of operations in each layer first. However, once you know how to compute the number of operations for one convolutional layer, one pooling layer, and one fully connected layer, you can easily compute the number of operations for the other convolutional, pooling, and fully connected layers. Then you just need to sum all these operations and express your time complexity as a function of the input (and probably number of layers).</p>
  <h3>Space complexity</h3>
  <p>If you also want to compute the space complexity, you just need to do the same thing, but as a function of the space that you use, i.e. how many variables you use to perform the convolution.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-28T08:00:10.423Z
Answers.Text: "so its size is n=9. How many operations did we perform with respect to the input's size? We performed 17 operations, so the time complexity O(2∗n)" What? 2 * 9 = 18. Or I am wrong?
Answers.UserDisplayName: user3352632
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-08T14:18:28.727Z
Answers.LastActivityDate: 2020-08-08T14:44:59.433Z
Answers.LastEditDate: 2020-08-08T14:44:59.433Z
Answers.UserDisplayName: nbro
Body: <p>How do I determine the computational complexity (big-O notation) of the forward pass of a <strong>convolutional</strong> neural network?</p>
  <p>Let's assume for simplicity that we use zero-padding such that the input size and the output size are the same.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-08T19:54:47.117Z
Comments.Text: "assume for simplicity that we use zero-padding such that the input size and the output size are the same." so you are assuming zero-filter as well?
Comments.UserDisplayName: k.c. sayz 'k.c sayz'
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-09T06:26:14.740Z
Comments.Text: @k.c.sayz'k.csayz' very funny! Anyway I assume the discussion about filters is going to be part of the answer.
Comments.UserDisplayName: mftgk
Tags: <convolutional-neural-networks><time-complexity><computational-complexity><space-complexity><forward-pass>
Title: What is the computational complexity of the forward pass of a convolutional neural network?
UserDisplayName: mftgk
ThreadText: # What is the computational complexity of the forward pass of a convolutional neural network?
  
  (Asked by: username_0 on 2020-08-07)
  
  How do I determine the computational complexity (big-O notation) of the forward pass of a **convolutional** neural network?
  
  Let's assume for simplicity that we use zero-padding such that the input size and the output size are the same.
  
  **Tags:** convolutional-neural-networks, time-complexity, computational-complexity, space-complexity, forward-pass
  
  > **Comments:**
  > **username_1**: "assume for simplicity that we use zero-padding such that the input size and the output size are the same." so you are assuming zero-filter as well?  
  > **username_0**: @username_1sayz'k.csayz' very funny! Anyway I assume the discussion about filters is going to be part of the answer.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-08-08. Score: 5
  
  ## What is the time complexity?
  
  The time complexity of an algorithm is the number of basic operations, such as multiplications and summations, that the algorithm performs. The time complexity is usually expressed as a function of the input's size $n$ (but this does not always have to be the case: for instance, you can express the time complexity as a function of the output's size).
  
  ## Example
  
  Rather than giving you a full answer to your question, I will try to help you by explaining, with the simplest example, how you should calculate the time complexity.
  
  For simplicity, let's assume that we have a kernel $\mathbf{H} \in \mathbb{R}^{3 \times 3}$ and input image $\mathbf{I} \in \mathbb{R}^{3 \times 3}$ (i.e. the kernel has the same dimensions as the input), we use a stride of $1$ and no padding. If we convolve $\mathbf{I}$ with $\mathbf{H}$, how many operations will we perform? The convolution is defined as a scalar product, so it is composed of multiplications and summations, so we need to count both of them. We have $9$ multiplications and $8$ summations, for a total of $17$ operations.
  
  \begin{align}
  \mathbf{I} \circledast \mathbf{H}
  &=
  \begin{bmatrix}
  i\_{11} & i\_{12} & i\_{13} \\
  i\_{21} & i\_{22} & i\_{23} \\
  i\_{31} & i\_{32} & i\_{33}
  \end{bmatrix}
  \odot
  \begin{bmatrix}
  h\_{11} & h\_{12} & h\_{13} \\
  h\_{21} & h\_{22} & h\_{23} \\
  h\_{31} & h\_{32} & h\_{33}
  \end{bmatrix}\\
  &=
  \sum\_{ij}
  \begin{bmatrix}
  i\_{11} h\_{11} & i\_{12} h\_{12} & i\_{13} h\_{13} \\
  i\_{21} h\_{21} & i\_{22} h\_{22} & i\_{23} h\_{23} \\
  i\_{31} h\_{31} & i\_{32} h\_{32} & i\_{33} h\_{33}
  \end{bmatrix}\\
  &=
  i\_{11} h\_{11} + i\_{12} h\_{12} + i\_{13} h\_{13} +
  i\_{21} h\_{21} + i\_{22} h\_{22} + i\_{23} h\_{23} +
  i\_{31} h\_{31} + i\_{32} h\_{32} + i\_{33} h\_{33}
  \end{align}
  
  ### Time complexity
  
  What is the time complexity of this convolution? To answer this question, you first need to know the input's size, $n$. The input contains $9$ elements, so its size is $n = 9$. How many operations did we perform with respect to the input's size? We performed $17$ operations, so the time complexity $\mathcal{O}(2\*n) = \mathcal{O}(n)$, i.e. this operation is linear. If you are not familiar with the [big-O notation](https://en.wikipedia.org/wiki/Big_O_notation), I suggest that you get familiar with it, otherwise, you will not understand anything about computational complexity.
  
  To calculate the time complexity in the case the input's dimensions are different than the kernel's dimensions, you will need to calculate the number of times you slide the kernel over the input. You can't ignore this (as I ignored the constant $2$ above) because the number of times you slide the kernel over the input depends on the input's size, so it's a function of the input. Anyway, the paper [A guide to convolution arithmetic for deep learning](https://arxiv.org/pdf/1603.07285.pdf) contains a lot of information about convolution arithmetic, so it will be helpful.
  
  ### Non-linearities, pooling and fully connected layers
  
  Note that, in the above example, I ignored the non-linearities and pooling layer. You can easily extend my reasoning to include these operations too. I also ignored the operations in the final fully connected layers. You can find how to calculate the number of operations in an MLP [in this answer](https://ai.stackexchange.com/a/13626/2444). If you also perform other operations or have other layers other than convolutional, pooling and fully connected, of course, you will also need to take them into account.
  
  ### Forward pass
  
  Moreover, the time complexity of the forward pass of a CNN depends on all these operations in these different layers, so you need to compute the number of operations in each layer first. However, once you know how to compute the number of operations for one convolutional layer, one pooling layer, and one fully connected layer, you can easily compute the number of operations for the other convolutional, pooling, and fully connected layers. Then you just need to sum all these operations and express your time complexity as a function of the input (and probably number of layers).
  
  ### Space complexity
  
  If you also want to compute the space complexity, you just need to do the same thing, but as a function of the space that you use, i.e. how many variables you use to perform the convolution.
  
  > **Comments:**
  > **username_3**: "so its size is n=9. How many operations did we perform with respect to the input's size? We performed 17 operations, so the time complexity O(2∗n)" What? 2 * 9 = 18. Or I am wrong?  
  
  ---
  
  