Time complexity of function minimizers for neural networks
The first paragraph in this tutorial, explains it pretty well. 

Also the time complexity will not grow linearly if you increase the size of your network. It will grow squared and so will the number of parameters.