[Type A] Chapter – 7 Class 12 CS – Sumita Arora Assignment | Q/A

An algorithm is well-defined and systematic method to approach specific task within some liabilities. This is sufficiently precise that can be programmed on computer.

Algorithm performance is the analysis of the working of algorithm and the efficiency of the algorithms on the given task which is majority decided by
(a) Memory used by algorithm.
(b) Time needed to rum complete algorithm.

The term Computational complexity refers to the calculation of the resources need by the algorithm to have result on given task and also the minimum resources needed to work more efficiently on the task.

This is basically measured by the time complexity and the space complexity.

Two types of factor affect the algorithm’s performance i.e. Internal and External Factors.

Internal Factors specify the algorithm’s efficiency in terms of
1. Time required to run the algorithm
2. Memory required to rum the algorithm

External Factors affects the performance of the algorithm to some extends as
1. Size of input to the algorithm
2. Speed of computer on which algorithm is running
3. Quality of compiler

Space Complexity : It defines the minimum memory size in total required to run the algorithm successfully.
Time Complexity : It defines the total time requires to have the final output from algorithm.

The Big-O notation is the most adopted way to define algorithm growth rate. The growth defines the working of algorithm on the variable and different input size. In this only upper bound is taken into consideration.
O(n!) means the algorithm run will take factorial of n steps where n is input size to algorithum.

The significance of Big-O is that it is the easy way for the comparison of the algorithms.

Worst-case complexity of the algorithm is defined by function as the maximum number steps requires on any instance of size N.
Best-case complexity of the algorithm is defined by function as the minimum number steps requires on any instance of size N.
Average-case complexity of the algorithm is defined by function as the average number steps requires on any instance of size N.

The worst case complexity is the considered complexity as it states the worst case working scenario of any algorithm.

(a) 5n5/2  as this is the dominant one. 
(b) 9n    as this is the dominant one in this case.
(c) n log2n  as this is the dominant one.
(d) n3/2  as this is the dominant one.

Order in the increasing worst behaviour 
10000 > n log2n > n5 > 2n >n!

Order in the increasing worst behaviour
2n > n0.5 > n log2n > n+n2+n3 

Total steps on input size 1000 =5((1000)^2) =5×10^6
Total time taken = 5X10^6X10^-9 = 5 millisecond

Total steps on input size 1000 =(1000)^3 =10^9
Total time taken = 10^9X10^-9 = 1 second

Total steps on input size 1000 =5*(1000)*log2(1000) =15000*log2(10)
Total time taken = 15000*log2(10)*10^-9 = 1 microsecond