Page 1 - Home Assignment-Algorithmic Efficiency
P. 1

Computer Science

                                                    Class – XII


                                  Topic: Idea of Algorithmic Efficiency


               1.  An efficient ___________________ lays the foundation of an efficient program.

               2.  A ___________________ is an algorithm encoded into some programming language.
               3.  __________________ is concerned with comparing algorithms based on the amount of

                   computing resources used.

               4.  Efficiency of a program can be evaluated on the basis of ______________ and

                   ________________.
               5.  _________________ is a measure of efficiency of algorithm.

               6.  For linear serach, the worst case time is __________________.

               7.  The input that makes algorithm run fastest is known as ______________ case.

                   (worst/average/best).
               8.  An algorithm whose run time is proportional to problem size is called

                   __________________ (linear/efficient) algorithm.

               9.  What is big O notation?
                                          2
               10. Compare O(n) with O(n ).
               11. What do you mean by efficiency of a program?

               12. What is faster linear search or binary search? Compare the two.

               13. Compare best, average and worst case efficiency. Explain through an example

               14. Write two different program for one problem and explain how efficient one program is
                   over other program.

               15. Compare the following two programs:

                        x=10                  x=10
                        for x in range(1, 11):  p=1
                           print(pow(n, x)    for x in range(1, 11):
                                                 p=p*x
                                                 print(p)
               16. Discuss the time complexity of

                       a.  Linear search
                       b.  Binary search

                       c.  Bubble sort
                       d.  Insertion sort
   1