What is the time complexity of the SGVB estimator?
Asymptotic running time analysis is not terribly useful for gradient descent used to train machine learning models.  In practical machine learning, we run gradient descent for some fixed number of epochs, e.g., 200 epochs; which takes time proportional to 200 times the size of the training set times the time per evaluation of the neural network.  That value 200 is arbitrary and set based on what achieves the best accuracy results, and there is little theoretical basis for choosing it.