n general, the time taken by an algorithm grows with the size of input eg sorting a thousand numbers take longer time than sorting 3 numbers. So it is traditional to describe the running time of algorithm as a function of the size of its input to do so we need to define the terms “Running Time” and size of input more carefully.
The Running Time of an algorithm on a particular input is the number of primitive operations or steps executed. A constant amount of time is required to execute each line of our pseudocode. One line statement may take different amount of time than
another statement of algorithm but we shall assume that each execution of the line takes Ci where Ci is a constant.
Input size depends on the problem being studied. Eg. such as sorting a sequence of integer array size`s input is number of item in the array. Another one multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in binary notation.
Algorithm heavily depends on the organization of data. There can be several algorithms for given problem.
The question is which of the algorithm is the best?
Performance of algo is measured in terms of
◦ Space complexity
◦ Time Complexity
We can specify growth of time requirements as a function of the input size.
Space complexity: Measurement of space requirement of an algorithm can be done at two different times:
a) compile time space complexity
b)Run time space complexity
i) code space
ii ) data space
iii) stack space
Time Complexity: Time complexity specifies the maximum time required for the execution of program as of the input size.
Let us assume time complexity T(P) is the time taken by program P and is the sum of the compile and execution time.
We can determine the no. of steps needed by a program to solve a particular problem by:
◦ Measuring the run time of an algorithm by counting the no. of steps multiply by constant time taken by the statement once.
Since space or memory space has become very cheap now days so we least bother about the space complexity of any algorithm our measure concern would be to find out the time complexity of any algorithm.
Computing Time Complexity of an Algorithm:
Time required by each statement depends on
◦ Time required for execution it once
◦ Number of times the statement is executed.
First compute execution time of all executable statements. Summation of all is the total time required for that algorithm.
Generally, when we sum the count of all the statements we get a polynomial.
And we are interested in only those statements which have the greatest count or power.
Let us start with a simple loop
Let the size of input data is n=1000
1. i=1 c1 1
2. loop(i<=n) c2 n+1(some statement here)
i=i+1 c4 n
3. End loop c5 1
Total time required for the algorithm: f(n)=c1*1+c2(n+1)+c3(n)+c4(n)+c5*1
So this is the polynomial equation whose variables highest power is one, means its time complexity is directly proportionate to the input size n.