Thursday, June 21, 2007

Time complexity and Space complexity of algorithms

I had just downloaded the SAP Memory Analyser and was impressed with its performance.
More information on this tool can be found here. Going thru their wiki, I read how they had taken pains to make critical operations have a time complexity of O(1).

Time complexity and Space complexity are terms used when dealing with algorithms. If the input size (problem size) for a algorithm increases, then how does it affect the time taken for the algorithm to complete and how how much more memory does it take?

If the time consumed by the algorithm is independant of the input size then the algorithm is said to be a complexity of O(1); i.e. a constant-time method. If the time taken is linear then it is known as linear-time method - O(n).

More information can be found at the following links:
http://pages.cs.wisc.edu/~hasti/cs367-common/
notes/COMPLEXITY.html
http://www.leda-tutorial.org/en/official/ch02s02s03.html