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

  • $\begingroup$ For 2) : $O(n^3)+O(n) = O(n^3)$, indeed. $\endgroup$ – Kuifje Oct 30 '19 at 9:55
  • 1
    $\begingroup$ 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). $\endgroup$ – LinAlg Oct 31 '19 at 1:00
  • $\begingroup$ @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. $\endgroup$ – user486789 Oct 31 '19 at 7:39
  • $\begingroup$ @Kuifje Thanks. $\endgroup$ – user486789 Oct 31 '19 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.