2
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ you need to know the size of your cnn $\endgroup$ – gunes Jun 3 at 9:31
2
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.