I am working on a resource allocation problem, which is convex and has several constraints, and I want to compare the computational complexity of the following algorithms.
1) The algorithm that uses iterative subgradient method through dual decomposition: It starts with initial values for dual variables and then, in each iteration, it finds the primal variables based on the dual variables and the Lagrangian function. Then it updates the dual variables using the subgradient of dual function (which is obtained using the primal variables in each iteration) and continues until the error between dual variables of two consecutive iterations is less than an epsilon. This algorithm takes a lot of iterations and has low convergence speed, which I think is mostly due to the fact that there are several dual variables.
2) A heuristic algorithm in which I divide the problem into convex subproblems with one constraint and use Golden Section search method for each of the subproblems. This algorithm has clear steps, e.g. O(NM), for dividing the main problem into subproblems and also the Golden section search for each of the subproblems converges very fast.
I need to show the difference of these algorithms in terms of complexity through simulations as well as theory. In theory, how can I compare the computational complexity of these algorithms? In other words, is there a systematic way as in the case of algorithms with fixed number of iterations (in which we say that for example one algorithm is O(XY) and the other is O(Ylog(X))) to show the difference in computational complexity?
Thanks in Advance.