Time Complexity of Algorithms And Space Complexity of Algorithms

 

Time Complexity :

Every algorithms requires some amount of computer time to execute its instruction to perform the task. This computer time required is called time complexity.

Definition :

The time complexity of an algorithm is the total amount of time required by an algorithm to complete its execution.

• The total time taken by the algorithm or program is calculated using the sum of the time taken by each of executable statement in algorithm or program.
• Time required by each statement depends on :

1.  Time required for executing it once.
2.   Number of times the statement is executed.

There are difference types of time complexities which can be analyzed for an algorithm :

1. Best Case :

• It is a measure of the minimum time that the algorithm will require for an input of size ‘n’.
• The running time of many algorithms varies not only for the inputs of different sizes but also for the different inputs of same size.
• For example in the running time of some sorting algorithms, the sorting will depend on the ordering of the input data.
• Therefore, if an input data of ‘n ’ items is presented in sorted order, the operations performed by the algorithm will take the last time.

 

1. Worst Case :

• It is a measure of the maximum time that the algorithm will require for an input of size ‘n’.
• Therefore, if various algorithms for sorting are taken into account and say ‘n’ input data items are supplied in reverse order for any sorting algorithms, then the algorithm will require n² operations to perform the sort which will correspond to the worst case time complexity of the algorithm.

1. Average Case :

• The time that an algorithm will require to execute a typical input data of size ‘n’ is known as average case time complexity .
• We can say that the value that is obtained by averaging the running time of an algorithm for all possible inputs  of size ‘n’ can determine average case time complexity.
• The computation of exact time taken by the algorithm for its execution is very difficult.
• Thus, the work done by an algorithm for the execution of the input of size ‘n’ define the time analysis as function f(n) of the input data items.

•  Example :

                    Int sum(int a, int b){
                    Return a+b;
                    }

• In above sample code, it requires 1 unit of time to calculate a+b and 1 unit of time to return the value.
• That means, totally it takes 2 units of time to complete its execution, And it does not change based on the input values of a and b.
• That means for all input values, it requires same amount of time i.e. 2 units.
• If any program requires fixed amount of time for all input values then its time complexity is said to be Constant Time Complexity.

Space Complexity :

• When we design an algorithm to solve a problem, it needs some computer memory to complete its execution.
• For any algorithm, memory is required for the following purposes…

1. Memory required to store program instructions.
2. Memory required to store constant values
3. Memory required to store variable values
4. And for few other things

Definition :

Total amount of computer Memory required by an algorithm to complete its execution is called as space complexity  of the algorithm.

• Generally, when a program is under execution it users the computer memory for three reasons. They are follows.

1. Instruction space :It is the amount of memory used to store compiled version of instructions.
2. Environmental Stack :It is the amount of memory used to store information of partially executed functions at the time of function call.
3. Data Space :It sis the amount of memory used to store all the variables and constants.

• Note :  when we want to perform analysis of an algorithm based on its space complexity, we consider only Data Space and ignore Instruction Space as well as Environmental  Stack. That Means we calculate only the memory required to store variables, Constants, Structures, etc.,
• To calculate the space complexity, we must know the memory required to store different data type values (according to the compiler).

        Example :

            Int square(int x){

            Return x*x;

            }

• In above piece of code, it requires 2 bytes of memory to store variable ‘x’ and another 2 bytes of memory is used for return value. (Assume int takes 2 bytes)
• That means, totally it requires 4 bytes of memory to complete its execution. And this 4 bytes of memory is fixed of any input value of ‘x’. This space complexity is said to be constant space complexity.
• That means, totally it require ‘2n+8’ bytes of memory to complete its execution. Here, the amount of memory depends on the input value of ‘n’. This space complexity is said to be Linear Space Complexity.

Note : 

• A data structue is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.
• different areas in which data strucutues are applied extensively are compiler Design, Operationg System, Database Management System, Statistical analysis package, Numberical Analysis, Graphicas, Artificaial Intelligence, Simulation.
• ADT is data declaration encapsulated with operations on it.
• Data structues are classified into linear and non-linear types.
• Need of data structure is essential for retrieving the information, manipulationg the data and storage utilization.
• An algorithm is a set of instructions to accmplish a particular task.
• Input, Output, Definiteness, Finiteness, Effectiveness are the characteristics of an algorithm.
• Time complexityy and space complexity are performance measures of a program.
• Analysis of an algorithm is done on the following basis :

1. Best case time Complexity .
2. Worst Case time Complexity.
3. Average Case time Complexity.
4. Time complexityy is the run-time required for program.
5. space complexityy is the memoryy or storage required for the program.
6. Big o, Are the notiations used in performace analysis.