Time and Space Complexity:
In order to solve any problem in computer science we write a program for that particular problem in any programming language, it is always recommended that we write some informal description of the solution which is called an Algorithm. By writing an algorithm that is in informal English like the language it becomes easier for us to understand how to communicate with the problem before implementation as it describes what we want to write.
But before implementing any algorithm as a program, we have to find out which algorithm is good and efficient enough for the problem because there can be more than one algorithms for solving one problem. So it becomes a challenge to choose the most efficient one.
But the question is how to determine the best algorithm for the solution. Well, let’s think about what should be the factors on which a solution may depend? Yes, the solution or the performance of the algorithm depends upon the time and space taken by the program. Space and Time complexity depends upon a lot of factors like the hardware, operating system, and processors. However, we don’t consider any of these factors while analyzing the algorithm. We will only consider the execution time of an Algorithm.
There are two parameters to calculate the efficiency of an Algorithm:
- Time Complexity
- Space Complexity
Time Complexity : Time Complexity is a function of how your time will grow as your input grows. This means the time taken by the problem estimated by counting the number of operations performed by the algorithm to complete the problem.
Time Complexity is the graph of time taken by the algorithm with respect to the number of inputs this is shown below in the figure.
As shown in the figure time complexity for function f(n) is represented by Asymptotic Notations like Theta(Θ), Big Oh(O),Omega(Ω)notations.
Asymptotic Notations are the Symbols that shows three cases for an Algorithm.
Let’s understand this concept with the help of one Example.
Ex- There is an array A={7,5,4,6,12,3,9} and we have to search some x element in the array. What should be our approach to solving this problem? There can be different possibilities but let’s say:
- If x=7 then the number of operations will be 1 only — best-case.
- If x=6 then the number of operations will be n/2 (where n is the total number of elements in an array) — Average Case.
- If x=9 then the number of operations will be n — Worst case.
As we have seen these three cases can be considered for calculating the efficiency of the Algorithm.
But there can be several ways of solving one problem which is characterized by these three notations. let’s take the same example but the sorted array {3,4,5,6,7,9,12}for searching an element in an array. There can be these two methods for solving this problem:
- Linear Search
- Binary Search
Linear Search:
We can search the x element by comparing it with the rest of the elements of the array one by one.
Binary Search:
Step 1:Then take the mid value and compare x with mid value if x is greater than the mid value .then jump to step 2otherwise jump to step 3.
Step 2:Then same algorithm can be applied on right half of the array.
Step 3.Then same algorithm can be applied on left half of the array.
Step 4. repeat until found the element x.
As we have seen the Binary search algorithm is more efficient compare to Linear search algorithm because linear search algorithm will have time complexity O(n) in worst case if x is the last element of the array which is 12 for this example.But if we are using binary search it will be O(log n).which is a significant difference if array size is big.So it is good to analyze the time complexity because working with large inputs it can be taking too much time for solving a problem without doing this analysis.
Space Complexity: Space consumed by the program is also an important factor for the analysis of an algorithm.
Space Complexity is a function of space consumed by the program as input increses.It is also represented by asymptotic notations.
Space Complexity is calculated by adding the space required for the following parameters:
1.Fixed:
Fixed part includes the space required by variable,constants and space for the program size.This part is not dependent upon size of the problem.
2.Variable:
Variable part includes the space required by variables and for some other data structures used for solving the problem like Stack,dynamic memory allocation etc.
