Understanding Time and Space Complexity
Abstract | Basics
Lets admit it, every student who has studied algorithms and analysed a few of them has come around these terms frequently. More often than not, “Time and Space Complexity” is a concept which will stick around with you for a good part of your life.
For every algorithm you read or come across in life, analysing space and time complexity is a standard practice. Every application developer or software developer has been through countless cycles of “optimization” and “development” before pushing their product to a public domain or usage.
So, what do these things exactly mean?
Defining Complexity -
Going by the standard definition, Complexity is, simply, “the state of having many parts and being difficult to understand to”.
However in the language of Computer Science, Complexity of an Algorithm is the amount of resources which are needed to run the algorithm.
Lets take a simple example. Assume that you are making a Lemonade.
What are your “resources” here?
> Water
> Lemon juice
> Sugar
Going by the same analogy, the resources required to create an algorithm, and to run it are :
1. Space (occupied) on the Computer
2. Time taken by that Computer to run that Algorithm.
Now lets jump back to our Lemonade example again. Lets assume we have to make 100mL of Lemonade and we have to make a choice amongst the given combinations.
Would you rather choose a combination with one litre of water and 5mL of Lemon Concentrate, or 50mL of water and 50mL of Lemon Concentrate
or 100mL of Water and 10mL of Lemon Concentrate?
The third combination seems to be the most suitable one. This is where optimization, or finding the desirable combination kicks in, and hence the need for Time and Space Complexity — to understand and create a desirable combination of these resources so that the algorithm you just designed works smoothly for all systems.
Complexities | Understanding and Analysing
Now that we have a basic understanding, lets get to the next part. We know that Space ( or memory occupied) and Time (consumed) are the two resources we need to take care of in an algorithm; however there a couple of other factors such as hardware, Operating System which we do not consider while analysing an algorithm.
Lets understand with an Example.
Given an array of length ‘x’ elements, check if element ‘p’ exists in the array or not.
for p: 1 -> X
if p = Array[x]
return TRUE;
else
return FALSE;The given pseudo code demonstrates that, if an element P exists in the given array then return the value, else; return FALSE — the value does not exist in the array. Each line here is an operation which takes approximately the same time for execution. For the sake of convenience, lets assume that each step takes time ‘s’ seconds to complete. There can be different cases which give us the answer.
Best Case:
Where the algorithm finds the element p in the first step itself and returns it. Time taken here will be 1 unit or just 1
Worst Case:
Where the algorithm traverses through the entire array to find element p but the element is not present in the array.
The time so taken will be ( N*s + k )
where N = the length of the array
s = execution time taken per operation
k = time taken by the return statement ( or a constant time)
Hence we see that as the length of array increases, so does the time taken.
While we have a basic understanding of Space and Time Complexity now, lets look at it in depth here, covering further topics such as Notations, order of growth, and the Average Case.
Hey! My name is Tanay Gandhi and I hope you liked this story! Do applaud and share it if you can. Connect with me using the given link
https://linktr.ee/tanay.gandhi
