Time & Space Complexity
what is time complexity?
According to Wikipedia, In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
In simple words time complexity is the measurement of time taken by a program to complete the process of running given by the input.
There can be more than one way to solve a problem, So we have to calculate which way is more faster and we can proceed according to that so that our algorithm can run much faster time, We can consider the following example for better understanding…
Here we can see that n is the input given to the method and the loop will run for n-2 times.
now here the loop runs for √n -2 times.
From these two methods we can conclude that the second method will take less time than the first method to complete hence the second on is better for fast execution.
How to measure Time Complexity ?
Here the loop will run n times
Time complexity: O(n)
Here the loop will run n² times
Time complexity: O(n²)
Time complexity represents using Mathematical notations.These expressions represents the time taken by a program to run the algorithm.
According to Wikipedia,
In computer science space complexity of an computer program is the amount of memory required to solve an instance of the computational problem as a function of the size of the input.
In other words it is the amount of memory used by an algorithm to execute and produce the result.
A good and optimized algorithm always take less space rather than a lengthy and complex algorithm, If we can write a program which will take less space then it will always be a better choice.
This method will take O(1) space because we used fixed number of variables.
This method takes O(n) space, The size of hiArray scales with the size of the input.
There are multiple ways to solve a problem so a good programmer should always write a program that will take less space.It will increase the quality of the code and it will give better performance.