Time and Space complexity demystified

Time Complexity

Here’s a good video by mycodeschool explaining the nitty-gritty of finding time complexity quickly for your code:

Space Complexity

Space complexity is a measure of how efficient your code is in terms of memory used.
Space complexity analysis happens almost in the same way time complexity analysis happens.

Don’t confuse space complexity with auxiliary space which is just temporary space used by your program. Below is an excerpt from Geeksforgeeks, clearing the air between auxiliary space and space complexity.

Auxiliary Space is the extra space or temporary space used by an algorithm.

Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.

For example, if we want to compare standard sorting algorithms on the basis of space, then Auxiliary Space would be a better criteria than Space Complexity. Merge Sort uses O(n) auxiliary space, Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n) though.

For example, consider the following code :

vector<int> V;
for (int i = 0; i < N; ++i) V.emplace_back(i);

The code snippet ends up creating a vector of size N. So, space complexity of the code is O(N).
Additional space / memory is measured in terms of the largest memory use by the program when it runs. That is to say, if you allocated O(N) memory, and later free it (auxiliary/temp memory), that does not make the space complexity of your program O(1), instead that O(N) will also be taken into account for space complexity calculations (Since, Space complexity includes both Auxiliary space and space used by input).

In short, space complexity is the total stack space required.

#Song of the day: Awesome cover of an age old song: House of the Rising Sun covered by the pure rock vocals of Candace Kucsulain from Walls of Jericho. 🙂

Advertisements

Here's your chance to type xoxo

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s