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

Here is class 12 computer science Unit 7 [Type A] solutions for Sumita Arora back exercise assignment. Below includes both textual and video solutions wherever required. View all the answers in assignment for chapter 7 and for all chapters here.

Watch all tutorials for chapter 7.

Q1: What is an algorithm? What do you understand by algorithm performance?

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.

Q2: What is computational complexity?

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.

Q3: Which factors affect an algorithm’s performance?

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

Q4: What are the different types of complexities that are considered?

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.

Q5: What do you understand by Big-O notation? What is its significance?

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.

Q6: What do you understand by best-case, worst-case, and average-case complexities? When are they considered?

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.

Q7: Determine the big-O notation for the following calculated complexity:
(a) 5n5/2 + n2/5 (b) 6 log2n +9n (c) 3n4 + n log2n (d) 5n2 + n3/2
(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.
Q8: Reorder the following efficiencies from the smallest to the largest:
(a) 2n (b) n! (c) n5 (d) 10000 (e) n log2n
Order in the increasing worst behaviour 
10000 > n log2n > n5 > 2n >n!
Q9: Reorder the following efficiencies from the smallest to the largest:
(a) n log2n (b) n+n2+n3 (c) 24 (d) n0.5
Order in the increasing worst behaviour
2n > n0.5 > n log2n > n+n2+n3 
Q10: Determine the big-O notation for the following:
(a) 5n5/2 + n2/5 (b) 6 log2n +9n (c) 3n4 + n log2n (d) 5n2 + n3/2

Q11: Given that the efficiency of an algorithm is 5n^2, if a step in this algorithm takes 1 nanosecond, how long does it take the algorithm to process an input of size 1000?

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

Q12: Given that the efficiency of an algorithm is n^3, if a step in this algorithm takes 1 nanosecond, how long does it take the algorithm to process an input of size 1000?

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

Q13: Given that the efficiency of an algorithm is 5nlog2(n), if a step in this algorithm takes 1 nanosecond, how long does it take the algorithm to process an input of size 1000?

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

Clear Doubts with Computer Tutor
In case you’re facing problems in understanding concepts, writing programs, solving questions, want to learn fun facts | tips | tricks or absolutely anything around computer science, feel free to join CTs learner-teacher community: students.computertutor.in

You cannot copy content of this page