Differences between time complexity and space complexity?

I have seen that in most cases the time complexity is related to the space complexity and vice versa. For example in an array traversal:

for i=1 to length(v)
    print (v[i])
endfor

Here it is easy to see that the algorithm complexity in terms of time is O(n), but it looks to me like the space complexity is also n (also represented as O(n)?).

My question: is it possible that an algorithm has different time complexity than space complexity?

The time and space complexities are not related to each other. They are used to describe how much space/time your algorithm takes based on the input.

function(list l) {
    print("i got a list");
}

function(list l) {
     for (node in l) {
        print(node);
    }
}

Note that both last examples take O(1) space as you don't create anything. Compare them to

function(list l) {
    list c;
    for (node in l) {
        c.add(node);
    }
}

which takes O(n) space because you create a new list whose size depends on the size of the input in linear way.

Your example shows that time and space complexity might be different. It takes v.length * print.time to print all the elements. But the space is always the same - O(1) because you don't create additional objects. So, yes, it is possible that an algorithm has different time and space complexity, as they are not dependent on each other.

Time and Space complexity are different aspects of calculating the efficiency of an algorithm.

Time complexity deals with finding out how the computational time of an algorithm changes with the change in size of the input.

On the other hand, space complexity deals with finding out how much (extra)space would be required by the algorithm with change in the input size.

To calculate time complexity of the algorithm the best way is to check if we increase in the size of the input, will the number of comparison(or computational steps) also increase and to calculate space complexity the best bet is to see additional memory requirement of the algorithm also changes with the change in the size of the input.

A good example could be of Bubble sort.

Lets say you tried to sort an array of 5 elements. In the first pass you will compare 1st element with next 4 elements. In second pass you will compare 2nd element with next 3 elements and you will continue this procedure till you fully exhaust the list.

Now what will happen if you try to sort 10 elements. In this case you will start with comparing comparing 1st element with next 9 elements, then 2nd with next 8 elements and so on. In other words if you have N element array you will start of by comparing 1st element with N-1 elements, then 2nd element with N-2 elements and so on. This results in O(N^2) time complexity.

But what about size. When you sorted 5 element or 10 element array did you use any additional buffer or memory space. You might say Yes , I did use a temporary variable to make the swap. But did the number of variables changed when you increased the size of array from 5 to 10. No, Irrespective of what is the size of the input you will always use a single variable to do the swap. Well, this means that the size of the input has nothing to do with the additional space you will require resulting in O(1) or constant space complexity.

Now as an exercise for you, research about the time and space complexity of merge sort

First of all, the space complexity of this loop is O(1) (the input is customarily not included when calculating how much storage is required by an algorithm).

So the question that I have is if its possible that an algorithm has different time complexity from space complexity?

Yes, it is. In general, the time and the space complexity of an algorithm are not related to each other.

Sometimes one can be increased at the expense of the other. This is called space-time tradeoff.

上一篇: 2 ^ n和n * 2 ^ n是否具有相同的时间复杂度？

下一篇: 时间复杂度与空间复杂度之间的差异？