Computational complexity results are often explained in intuitive terms as statements about the possible efficiencies of algorithms to solve certain classes of problems.

However, on a more formal level, all (many?) results actually build on the underlying notion of Turing machines, which provides a precise way to define computation.

My question is then: can all computational complexity statements be fully expressed in terms of lines of (pseudo-)code?

If so, would that mean that one should state all results building on a finite set of "elementary operations" that are allowed in the programming language under consideration? What would be the "elementary operations" in such a context?

  • $\begingroup$ This may be of interest. $\endgroup$ – koverman47 Jul 20 '18 at 22:05
  • $\begingroup$ Are you aware that big O notation is used to describe algorithm complexity? $\endgroup$ – beroal Jul 21 '18 at 12:36

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.