big-\(\mathcal{O}\) analysis of convolutional neural network architecture

by Dimitros Leventis

Here, we study how convolutional neural networks process images, and how to reason about their computational efficiency using Big−O notation.

deliverables

1. Understanding Convolutional Neural Networks (CNNs)

Introduce the structure and purpose of CNNs: what they are, why they’re used in image processing, and how they differ from regular neural networks.

Requirements

• Define a neural network and what a layer is in simple terms.
• Explain how a CNN processes an image (pixels, filters, feature maps).
• Describe the role of convolutional layers, pooling layers, and activation functions.
• Bonus. Include a hand-drawn or digital diagram of a simple CNN with labels.

2. CNN as an Algorithm

Write down the CNN as a step-by-step algorithm that transforms an input image into a prediction. Write down its input, processing steps, and output, similar to how you’d describe a sorting or searching algorithm.

Requirements

• Describe the input: what does the CNN receive? (e.g., a \(32 \times 32\) grayscale image)
• Break the CNN pipeline into clear algorithmic steps:
  • Convolution
  • Activation (e.g., ReLU)
  • Pooling (if used)
  • Fully connected layer / classification step

• Write it like a procedure:

  Input \(\rightarrow\) Step 1 \(\rightarrow\) Step 2 \(\rightarrow\) … \(\rightarrow\) Output

• Compare this to a classical algorithm. What makes it similar, and what’s different?

3. Big-\(\mathcal{O}\) Analysis of a Simplified CNN

Apply Big-\(\mathcal{O}\) notation to analyze how computation scales in a basic CNN as input size and layer depth increase.

Requirements

• Briefly define Big-\(\mathcal{O}\) notation with a real-life analogy.

• As an example, use a fixed \(32 \times 32\) grayscale image.

  Version A: 1 conv layer with 8 filters of size \(3 \times 3\) \(\rightarrow\) output \(30 \times 30 \times 8\)

  Version B: add a second conv layer with 16 filters \(\rightarrow\) output \(28 \times 28 \times 16\)

  Calculate the number of operations required for each convolutional layer, focusing on the convolution steps¹.

• Bonus. Derive the Big-\(\mathcal{O}\) complexity for the CNN in terms of input size \(n \times n\), number of filters \(f\), and kernel size \(k\).

4. Reflection

Consider the tradeoffs in designing deep networks: efficiency, accuracy, training complexity.

Requirements

• Summarize what you learned about how complexity grows with deeper architectures.
• Identify limitations of Big-\(\mathcal{O}\) analysis (e.g., it ignores constants, parallelization).
• Reflect on what’s more important in real-world AI: speed, accuracy, memory?

Resources

• But what is a convolution? 3Blue1Brown.
• Introduction to CNNs. GeeksforGeeks.
• What are CNNs? IBM Tech.
• Big-\(O\) analysis. GeeksforGeeks.²