Algorithm Complexity

I have been going through sorting and searching algorithms and their implimentations in C language.

I found two terms Time complexity & Space complexity. But most of the sorting and searching algorithms speaks more about time complexity.

Those algorithms use lot of variables (space) and mentioning nothing about the space complexity.

Is space complexity NOT a factor to consider in sorting and searching algorithms??? :confused:

What are your views??

It depends on what you're sorting, and how much you're sorting. But look at it this way: QuickSort is an inplace sort - all extra space you use comes from the stack of the recursive calls. Its space complexity is therefore O(log n), with a very low constant. MergeSort is usually done using a scratch buffer. Its space complexity is O(n), with a somewhat larger O.
In both cases, the time complexity is O(n log n). That's more.

In addition, memory is cheap, but time often is not. Another point is that once the sorting is done, the used memory is freed. You'll never regain the used time.

Only systems that handle more data than fits into RAM, like databases, consider space complexity. But that's only because to those systems, space complexity IS time complexity, because it takes so long to write and read external storage.

Does that mean I dont need to bother about space complexity while implimenting sorting and searching algorithms as C programs?

Thanks CornedBee

>Does that mean I dont need to bother about space complexity
Unless you're trying to invent a sorting algorithm, space complexity is just a matter of the needs of your program and picking the right algorithm to fit the job. For example, sometimes you can get away with bubble sort, but other times you need something with better time complexity. Usually stability is the deciding factor in choosing mergesort, even though it has an undesirable space complexity. It all depends on what you're doing. :) Space complexity plays a bigger part in searching because the speed of searching can vary greatly depending on how you store the data. Once again, how much it matters is up to your needs.

Thanks Slacker.