I would like to know the most rigorous definition of the time- or space complexity of algorithms. I mean for example Corman et al. uses notations like $n+O(n)$ which seems weird as $O(n)$ is defined to be a set in their book. The book "Asymptotic Analysis" by Murray uses functions in complex space but programmers are interested only non-negative integers. So what should a mathematician answer if some computer science student wants to ask rigorous way to do time- and space complexities of an algorithm? For example the Wikipedia site https://en.wikipedia.org/wiki/Big_O_notation writes "Let f be a real or complex valued function". Do we need to assume that algorithms use complex valued functions? How one can formalize the set of algorithms?

  • 4
    $\begingroup$ It takes a good amount of work to define these things rigorously. But the standard starting point is to define algorithms to be Turing machines, and then the running time of the algorithm is the number of steps taken by the Turing machine. This is pretty arbitrary, because there are a lot of other ways to define computation, but I believe it turns out most different implementations have at most a polynomial time difference in the time taken by the algorithm, and this allows you to define classes like P, NP etc. But I'm not an expert here so I'll allow someone else to answer. $\endgroup$ – Jair Taylor Apr 10 '18 at 17:31
  • 3
    $\begingroup$ Note that one hardly ever specifies an exact complexity of an algorithm. For example, we say that prime factorization of $n$ by trial division takes $O(\sqrt n)$ time; but the actual runtime for $n=2^k$, for example, will only be $O(\log n)$. Instead of making unmanageably many case distinctions, one gives upper (and lower) bounds, and for that end, Big-Oh notation is great. Additionally, the same Big-Oh class will apply (i.e., the actual runtimes will all be in the same st of functions) if we code an algorithm for a machine where basic operations such as $+$ and $\times$ time differently . $\endgroup$ – Hagen von Eitzen Apr 10 '18 at 17:37
  • $\begingroup$ Space complexity shouldn't be mixed with time complexity, unless you deal with formal computations. $\endgroup$ – Jean Marie Apr 10 '18 at 18: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.