Preview lessons, content and tests

Computer Science & Programming solved. All in one platform.

1. To trial the platform and take tests, please take a few seconds to SIGN UP and SET UP FREE.

2. Searching for something specific? See our text overview of all tests. Scroll right for levels, and lists.

3. Student and Teacher User Guides |  Schemes of Work |   Real Teacher use Videos |


Join 36000+ teachers and students using TTIO.

Timewise and Spacewise comparison

An algorithm is a step-by-step set of instructions to solve a specific problem and it is important to understand that the same problem can be solved with a variety of algorithms. How can we measure the efficiency of a given algorithm, so it can be compared with a different algorithm which solves the same problem?

Spacewise Complexity

That is the amount of (memory) space the algorithm will take up before it terminates with the correct solution.

In order to identify the space-wise efficiency we need to look at the amount of data structures used as the algorithm is running. When considering space-wise efficiency, the aim is to utilise data structures which take up the least amount in memory.

Examples:

  • populating a list with variables of type real will be space-wise inefficient, when it is clear that only whole numbers (integers) will ever be needed to solve the problem.
  • initialising an array with a length of 1000 will be space-wise inefficient, when it is clear that the maximum elements to be stores will be 100.

Timewise Complexity

This is the amount of time it takes for the algorithm to terminate with the correct solution.

Any measure of time will depend on other factors, like

  • the particular version and type of programming language used to implement the algorithm;
  • the hardware specification on which the implementation will be running;
  • and of course the input to the algorithm, e.g. searching through a very very large set will take longer that searching through a short set and searching for an item which does not exist in a set will take longer than searching for an item which is present in a given set.

Time Complexity (with examples from Facebook)

Time Complexity

Algorithm Data Structure Time Complexity
    Best Average Worst
Quicksort Array O(n log(n)) O(n log(n)) O(n^2)
Mergesort Array O(n log(n)) O(n log(n)) O(n log(n))
Heapsort Array O(n log(n)) O(n log(n)) O(n log(n))
Bubble Sort Array O(n) O(n^2) O(n^2)
Insertion Sort Array O(n) O(n^2) O(n^2)
Select Sort Array O(n^2) O(n^2) O(n^2)
Bucket Sort Array O(n+k)

www.teachyourselfpython.com