Welcome learners. This post Performance Analysis-Time and Space Complexity will let you know about several things. You will come to know about what is time complexity?. What is space complexity?. On whole a brief introduction to the performance analysis of algorithm. You can also refer to my previous posts Two Pointers Technique/Approach, What is Binary Search?, Greedy Algorithm, Importance of DSA if needed.
Performance Analysis
There is a criteria for judging algorithms that have a direct relationship to performance. These have to do with their computing time and space required. Time and space directly links with the performance of your algorithm. So time and space complexity are two major criteria to consider.
Space complexity
The space complexity of an algorithm is the amount of memory it need to run for completion. i.e. how much space will your algorithm take between start and end of your algorithm.
Your algorithm space is the sum of the following components:
1. A fixed path i.e. independent of the characteristics (ex: number, size) of the inputs and outputs. This part typically includes the instruction space, space for sample variables and space for constants.
2. A variable part consists of the space occupied by component variables. Component variables size depends on the particular problem instance being solved. And also the reference variables space (i.e. depends on the instant characteristics).
So The space requirement of your algorithms is S(P)= C + Sp
C = constant
Sp = Instant and variable characteristics
Time complexity
The time complexity of an algorithm is the amount of time it needs to run for completion. You can define the time complexity of any algorithms by counting the no. of program steps instead of determining the exact no. of operations.
A program step is defined as a syntactically or semantically meaning full segment of your program that has an execution time i.e. independent.
The no. of steps of any program statement depends on the kind of statement. For example comments count as zero steps. And assignment statement (not involving any calls to other algorithms) is counted as one step. In an iterative statement such as “for” ,”while”, “repeat”, “until” statements, we consider the step count only for the control part of the statement.
Time and Space Complexity tutorial hackerearth
