I am analyzing the computational complexity of an algorithm that includes as a step the solution of a linear subproblem of n variables and n constraints.
The linear subproblem can be solved by the karmarkar's interior point method. In this case the complexity of this step is $O(n^{3}L)$, where $L$ is the bit size.
I have two questions:
- Why is the size of bit included in the complexity of karmarkar's method? (Could one write just $O(n^{3})$?)
2.Knowing that the complexity of the other steps of my algorithm is of $O(n)$, what is the total time complexity of the algorithm? Is it $O(n^{3})$?