# What is Big-O complexity of classifying an image using CNN?

If i have an image consisting of n pixels what will be the complexity of classifying it using a convolutional neural network, expressed in big-o notation? (assuming my cnn is already trained)

• you need to know the size of your cnn – gunes Jun 3 at 9:31

$$O(n)$$
In a CNN, the number of features in each feature map is at most a constant times the number of input pixels $$n$$ (typically the constant is < 1). Convolving a fixed size filter across an image with $$n$$ pixels takes $$O(n)$$ time, since each output is just the sum product between $$k$$ pixels in the image, and $$k$$ weights in the filter, and $$k$$ doesn't vary with $$n$$. Similarly, any max or avg pooling operation doesn't take more than linear time in the input size. Therefore, the overall runtime is still linear.