This content originally appeared on DEV Community and was authored by Vishwa.R
Before starting this short and brief blog, I have one important thing to do, guessed it?
A BIG THANKS TO ALL MY FOLLOWERS, you guys just encourage me to share my little knowledge far and wide. Thanks once again!
So, let us get into today's topic Space and Time Complexity.(Yeah, it's not physics). We'll see What are they?, Why are they used? And How to use them?
Let's start with our first question,
What are they?
Time complexity:
Time complexity is nothing but the amount of time taken by an algorithm for its execution. It is a Time Function (Don't mind a bit of maths here and there).
Space complexity:
Space complexity is nothing but the amount of memory used by the algorithm for its execution. Here, one should not include the actual program size, but should consider only the space or memory needed for execution with respect to the inputs passed.
So with this we proceed to our next question, what is the need for these, let's see about it below.
Why are they used?
So why the need for these Time and Space complexities? Are they that important?
The answer is YES, they are very important and are vital deciding factors in terms of efficiency of the algorithm we design.
Time complexity calculations shows us some great insights, regarding time, like how much amount of time the algorithm will take and is it suitable for processing large inputs and real word data.
Note:
One should note that, time complexity does not give the exact time of execution, as it depends on many factors like OS, programming language and Hardware used. Time complexity gives a time function from which we can infer some valuable insights.
Whereas, space complexity tells us a different aspect of the algorithm regarding how much memory or space it'll utilize, and thus it helps in predicting the suitability of its execution on real hardware prior to actual execution.
How to use them?
I'll make it clear that, I won't be diving into exact mathematics behind these, but I'll try to explain as brief as possible here. (If you are really interested to know the maths, just comment on the blog, I would be happy to prepare a series explaining exact steps easily)
So here we sprinkle some exotic JavaScript programs ? for our understanding. Let's start with this simple program,
So here in this program, we are swapping the values of a and b, for that we use a temporary variable called temp. Let's find the Time and Space complexities for this simple program.
Time Complexity:
Here I mention each line with line numbers like L1 and L5. We can also ignore the function definition and function call, as we only care about the logic part. Because, we perform time and space analysis only on algorithms and algorithms only care about logics. So we start from L3, we are doing an initialization here, so it will take less time compared to loops.(loops run over and over and spend high amount of time). We know that the initialization statement uses a constant unit of time (the smallest possible unit, we take it as 1). So the next statement at L4 performs an assignment operation, and it also uses a constant time (we take it as 1). And next we at last do another assignment operation at L5, which also uses a constant time, like the previous statements.
So that's it pretty simple right!, now we just add all those, and we get 1+1+1 = 3 which is also a constant. So we infer that this program runs in constant time. We also write the time function as,
T(n) = O(1) → here 1 represents constant.
There are many notations we could use to better represent the time function, we'll see them in a series of blogs, if you guys are interested.
So, that is all with time. Let's jump into space complexity.
Space complexity:
Here, we take account for all the variables used, as variables are the memory occupiers. In our very short swapping program, we've got 3 variables. Let us list them below,
1. a → occupies 1 space
2. b → occupies 1 space
3. temp → occupies 1 space
As all the variables occupy 1 space for each of themselves, which means they occupy constant amount of space or memory for their execution. We add all those values 1+1+1 = 3 and we get 3, which is also a constant value, so we can write the space function as below.
S(n) = O(1) → Here also 1 represents constant
So that's it, we've found the time and space functions for a simple swapping program. It would be a little more work, if the program involves arrays and loops. We'll see about loops maybe in the next blog.
Hope you enjoyed the blog, if you have any comments, just comment, I would be happy to see them, if you like the blog then give a ?.
Want a whole series on Time and Space complexity? Please leave a comment about your opinion. Thanks for reading and have a nice day!
Attributions :
Cover image :
Photo by Pierre Bamin on Unsplash
Combined by ME for better context to the title :-)
Photo by Aldebaran S on Unsplash
This content originally appeared on DEV Community and was authored by Vishwa.R
Vishwa.R | Sciencx (2021-08-04T18:55:51+00:00) Time and Space, but not relativity :-). Retrieved from https://www.scien.cx/2021/08/04/time-and-space-but-not-relativity/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.