Search code examples
algorithmmemorytime-complexitycomplexity-theory

What is the definition of time and memory complexity of algorithm?


Looking for a general understanding of the time and memory complexity of any algorithm.


Solution

  • When we talk about the thing-complexity of an algorithm, we are talking about what general set of functions that thing grows as, as the size of the input grows.

    For time, this is pretty obvious, it is the time (well, normally "number of operations") that it takes to execute an algorithm.

    For memory, we normally refer to the extra memory needed for the algorithm. This covers things like "explicit temporary variables", "stack" and others.

    For complexity, we frequently use "big-O" notation. The general form is f(n) ∊ O(g(n)), by which we mean that the (exact) function that we have is part of a set, such that there is an m, for which all k ≥ m, and a c, such that f(k) ≤ c * g(k).