Analysis of Algorithm
When we are designing any algorithm the primary concern is not only solving the problem, as we know that to solve any problem there could be n number of ways to approach it, but also on how to solve it efficiently and effectively. So for the analysis of algorithms we need to have sound understanding of Space and Time complexities.
Space Complexity
For any algorithm space complexity is the amount of space required to run the program. It is the function describing the amount of memory (space) an algorithm takes in terms of the amount of input to the algorithm.
Sometimes we do confuse space complexity with auxiliary space, but Auxiliary Space is the temporary space or extra space used by algorithm. Space complexity includes both Auxiliary space and space used by input.
The space required by any algorithm comprises of two components a fixed part and a variable.
A fixed part that is independent of the characteristics (e.g., number size) of the inputs and the outputs. This part typically includes the instruction space(i.e. space outside for the code), space for simple variables and fixed-size component variables(a.k.a. aggregate), space for constants, and so on.
A variable part that consists of the space needed by component variables whose size is dependent on the particular problem instance being solved, the space needed by referenced variables (To the extent that this depends on instance characteristics), and the recursion stack space (as this space depends on the instance characteristics).
S(P) = c +Sp(instance characteristics)
In other words,
Space = Fixed Part + Variable Part
where, Fixed part is input space and space used by local variables and the variable part is Auxiliary Space.
Case 1:
def calculate(a,b,c):
return a+b/cS(p) = 1 + 1 + 1 = 3 ==> O(1)
Case 2:
def sum(a, n):
s = 0
for i in range(n):
s += a[i]
return sS(p) = (n*1 + 1 + 1) + 1 ==> O(n) and auxiliary S(p) = O(1)
Case 3:
def Rsum(a,n):
if n <= 0:
return 0
return a[-1] + Rsum(a[:-2], n-1)(# of stack frames)*(space per stack frame)
When the function calls itself there are 3 things that are stored in the stack. The array pointer a, The size of the array, n and The value at the last index a[n].
So space per stack frame equals to sizeof(a)+sizeof(n)+sizeof(a[n])
This function calls itself till n becomes 0 so, number of stack frames = n (from n-1 to 0)
Get Riyashi Chandak’s stories in your inbox
Join Medium for free to get updates from this writer.
Therefor the amount of space required to store execute is n times the space required to store above 3values once,
i.e., (n)*{sizeof(a)+sizeof(n)+sizeof(a[n])}
Since the value in the braces remain a constant for a particular i/p,
we say that the space complexity of this is directly proportional to n. i.e auxiliary S(p) = O(n).
Time Complexity
Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input.
To simplify we can say time complexity is nothing but efficiency with which the program runs or the amount of time taken by any program to be process a given input.
“The time T(P) taken by a program P is the sum of the compile time and the run (execution) time. The compile time does not depend on the instance characteristics.” — Fundamentals of Computer Algorithm by Ellis Horowitz.
There are various ways in which time complexities can be calculated, one of the most common is the Big ‘Oh’ notation, alternatively we can also use Omega, theta or Little ‘oh’ notations.
This removes all constant factors so that the running time can be estimated in relation to N, as N approaches infinity. In general you can think of it like this :
statement;Above we have a single statement. Its Time Complexity will be Constant. The running time of the statement will not change in relation to N.
for(i=0; i < N; i++)
{
statement;
}The time complexity for the above algorithm will be Linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.
for(i=0; i < N; i++)
{
for(j=0; j < N;j++)
{
statement;
}
}This time, the time complexity for the above code will be Quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.
while(low <= high)
{
mid = (low + high) / 2;
if (target < list[mid])
high = mid - 1;
else if (target > list[mid])
low = mid + 1;
else break;
}This is an algorithm to break a set of numbers into halves, to search a particular field(we will study this in detail later). Now, this algorithm will have a Logarithmic Time Complexity. The running time of the algorithm is proportional to the number of times N can be divided by 2(N is high-low here). This is because the algorithm divides the working area in half with each iteration.
void quicksort(int list[], int left, int right)
{
int pivot = partition(list, left, right);
quicksort(list, left, pivot - 1);
quicksort(list, pivot + 1, right);
}Taking the previous algorithm forward, above we have a small logic of Quick Sort(we will study this in detail later). Now in Quick Sort, we divide the list into halves every time, but we repeat the iteration N times(where N is the size of list). Hence time complexity will be N*log( N ). The running time consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm is a combination of linear and logarithmic.
Happy Understanding!
References:
Photo credits to the owner.
http://exploreshaifali.github.io/2014/02/13/Space-Complexity/
https://www.studytonight.com/data-structures/time-complexity-of-algorithms








