# complexity of linear programming

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:

1. 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})$$?

• For 2) : $O(n^3)+O(n) = O(n^3)$, indeed. – Kuifje Oct 30 '19 at 9:55
• For 1): did you read the remarks on $L$ in "A new polynomial-time algorithm for linear programming" by Karmarkar? For 2): that depends if the linear program is nested (i.e., executed repeatedly or just once). – LinAlg Oct 31 '19 at 1:00
• @LinAlg I read this remark where they claim the importance of $L$, but if I understand correctly it is not wrong if we remove it as in the Gauss method!! Is it correct?? For 2: the execution is repeated until convergence, but I want to analyse the complexity of one iteration. – user486789 Oct 31 '19 at 7:39
• @Kuifje Thanks. – user486789 Oct 31 '19 at 7:43