Difference between time complexity and computational complexity

Problem Detail: 

For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them?

I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm.

Asked By : Median Hilal

Answered By : Luke Mathieson

Computational complexity is just a more general term, as time is not the only resource we might want to consider. The next most obvious is the space that an algorithm uses, and hence we can talk about space complexity, also as a part of computational complexity. Indeed we can do this for any measure you care you use, of course some measures are more useful than others.

So counting the number of steps that an algorithm takes in the worst case gives a time complexity bound for the problem it solves, counting how much memory/how many tape cells it uses gives a space complexity bound etc. etc.

Remember also that if you want to be strict, complexity refers to the problem, not the algorithm, so a problem has complexity bounds, an algorithm has resource bounds (running time, space use...). It's just a matter of definitional formality, complexity theory deals with problems. Yes, algorithms are a key tool for analysing problems and complexity and algorithmics are closely tied together, but formally we wouldn't say Merge-Sort (an algorithm) is in $P$, it's the problem $\mathsf{Sorting}$ which is in $P$. Merge-Sort uses certain resources ($O(n\log n)$ steps for example). The resource bound and correctness of the algorithm imply the complexity (upper) bound for the problem, but they're different things. $\mathsf{Sorting}$ is also $TC^{0}$-complete under $AC^{0}$-reductions, this complexity bound can only really be stated for a problem (but does have algorithmic implications).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42044