{"id":129,"date":"2018-07-19T06:13:02","date_gmt":"2018-07-19T06:13:02","guid":{"rendered":"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=129"},"modified":"2018-07-19T06:43:37","modified_gmt":"2018-07-19T06:43:37","slug":"computational-complexity","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/chapter\/computational-complexity\/","title":{"rendered":"Computational Complexity"},"content":{"raw":"
\r\n

This module 31 focuses on introducing theory of computational complexity. The module discusses how to find limitations of algorithms in terms of upper and lower bounds. The module also discusses the ways of finding lower bound of the algorithms. The objectives of this module are<\/p>\r\n \r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the concept of Computational Complexity\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To Understand Upper bound theory\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To Understand Lower Bound Theory\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To know about Proof of Lower Bound Theory\r\n\r\n \r\n\r\nComputational Complexity<\/strong>\r\n\r\n \r\n

There are two types of complexity theory. One is related to algorithm complexity analysis called algorithmic complexity theory and another related to problems called computational complexity theory.<\/p>\r\n \r\n

Algorithmic complexity theory aims to analyze the algorithms in terms of the size of the problem. In modules 3 and 4, we had discussed about these methods. The size is the length of the input. It can be recollected from module 3 that the size of a number<\/strong> n<\/em> is defined to be the number of binary bits needed to write n. For example,<\/em> Example: b(5) = b(1012) = 3. In other words, the complexity of the algorithm is stated in terms of the size of the algorithm.<\/p>\r\n \r\n

Asymptotic Analysis <\/strong>refers to the study of an algorithm as the input size reaches a limit and analyzing the behaviour of the algorithms. The asymptotic analysis is also science of approximation where the behaviour of the algorithm is expressed in terms of notations such as big-oh, Big-Omega and Big- Theta.<\/p>\r\n \r\n

Computational complexity theory is different. Computational complexity aims to determine lower bound on the efficiency of all the algorithms for a given problem and Computational complexity is measured independently of the implementation. In simple words, computational complexity is about the problem and not the algorithm.\u00a0In computational complexity theory, two things are important. One is the upper bound and another is the lower bound of the algorithm. Lower and upper bounds <\/span>defines the limits of the algorithm. Upper bound indicates the worst case performanc e of the algorithm and lower bound indicates the best case performance of the given algorithm.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nUppe r bound of the Algorithm<\/strong>\r\n\r\n \r\n

Upper bound of the algorithm is the pessimistic view of the algorithm. It can be used to indicate worst, average and best case analysis of the algorithm and often expressed as a function. It can be viewed as a proof that the given problem can be solved using at most \u2018n\u2019 operations, even in the worst case.<\/p>\r\n \r\n

The upper bound for an algorithm is used to indicate the upper or highest growth rate. Normally the algorithm is measured with respect to best, worst and average case analysis. It can be said based on literature [1,2,3] that \u201cthe running time grows at most this much, but it could grow more slowly\u201d.<\/p>\r\n \r\n

In other words, the cost also is represented as a function. How to determine the upper bound of an algorithm? Let A be the algorithm to be analyzed and if In is set of all possible inputs to Algorithm A and fA (I) is the resource cost of the algorithm when given input I ranges over I<\/em>n<\/em> . Then, the following costs can be defined:<\/p>\r\n \r\n\r\n \r\n\r\nworst cost (A) = max I\u00a0 \u00ce I<\/em>n<\/em>\u00a0 fA(I)\r\n\r\n \r\n\r\nBest\u00a0 cost (A) = min I \u00ce I<\/em>n<\/em>\u00a0\u00a0 fA(I)\r\n\r\n \r\n\r\n \r\n

One can say the upper bound of the algorithm succinctly using Big-oh notation [4]. It can be described for run time T(n) of the given algorithm as follows: Let T(n) a non-negatively valued function, then T(n) is in set O(\u0192(n)) if there exists two positive constants c and n0 such that T(n)<\/p>\r\n \r\n\r\n\u2264 c\u0192 (n) for all n > n0. Here, \u00a0\u00a0and .\r\n\r\n<\/div>\r\n \r\n

For example, for towers of Hanoi, the upper bound is is given as f(n) = 2n-1. One can verify that by substituting different values for \u2018n\u2019 and verify it matches with the number of disks movement to move dist from source peg to destination peg. This is shown in table 1.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

\r\n\r\nFrom this one can guess, that the upper bound is 2n-1.\r\n\r\n \r\n

One can also recollect from modules 3, 4 and 5, we called this as mathematical Induction and using which the upper bound is correctly established.<\/p>\r\n \r\n\r\n \r\n\r\nLower Bound Theory<\/strong>\r\n\r\n \r\n

Lower bound is for problems and finding it is difficult compared to upper bound of the algorithm. Lower bound is the smallest number of operations necessary to solve a problem over all inputs of size n. In short, it is \u201cAt least this much work to be done\u201d [2,3].<\/p>\r\n\r\n<\/div>\r\n \r\n

Lower bound is an indication of how hard the algorithm is! It is done for problems and not algorithms. In other words, it is obtained the \u201cbest\u2019 algorithms that is required to solve the given problem. Let M be the model, and if Am is the set of all algorithms for problem P, then the Lower bound on the worst cost of P is given as follows:<\/p>\r\n \r\n\r\nmin A belongs Am { max fA(I)}\r\n\r\n \r\n\r\nSome of the examples of the lower bound are given as follows:\r\n

    \r\n \t
  1. Number of comparisons needed to find the largest element in a set of n<\/em> numbers<\/li>\r\n \t
  2. Number of comparisons needed to sort an array of size n<\/em><\/li>\r\n \t
  3. Number of comparisons necessary for searching in a sorted array<\/li>\r\n \t
  4. Number of multiplications needed to multiply two n<\/em>-by-n<\/em> matrices<\/li>\r\n<\/ol>\r\n \r\n\r\nLower bound for an algorithm with run time T(n) is given formally as follows:\r\n\r\n \r\n\r\n \r\n\r\nT(n) a non-negatively valued function, T(n) is in set \u03a9(\u0192(n)) if there exists two positive constants c and n0 such that T(n) \u2265 c\u0192(n) for all n > n0.\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n
    \r\n\r\nLower bounds can be of two types.\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Worst Case Lower bound\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Average case Lower bound\r\n\r\n \r\n\r\n \r\n\r\nIt must be observed that the actual cost is in between Upper and Lower bound and lower bound indicates how optimal the algorithm is! A best scenario is lower bound = upper bound or nearly equal and if not, then better search for solution continues.\r\n\r\n \r\n\r\nLet us discuss about sorting problems where these theories can be applied.\r\n\r\n \r\n\r\n \r\n\r\nSorting proble ms<\/strong>\r\n\r\n \r\n\r\nThere are two models for finding bounds for sorting problems. They are\r\n
      \r\n \t
    • \u00a0Exchange Model<\/li>\r\n \t
    • Comparison model<\/li>\r\n<\/ul>\r\n<\/div>\r\nLet us discuss about them now.\r\n\r\n \r\n\r\nExchange Model<\/strong>\r\n\r\n \r\n

      In exchange model, the input consists of \u2018n\u2019 items and the only operation allowed is exchange at a cost of 1 step [2,3]. All other operations like comparison, examining item is considered as cost free operations. In exchange model, n-1 exchanges are required. Therefore, the upper Bound is n-1 exchanges are sufficient and for lower bound, n-1 Exchanges are necessary in the worst case . In short, n-1 represents the cost required for lower and upper bound.<\/p>\r\n \r\n\r\nComparison Model<\/strong>\r\n\r\n \r\n

      In comparison model, the important operation is comparison operations [3]. In this model, the input consists of \u2018n\u2019 items and the only operation allowed is comparison information as yes \/ No. Apart from comparison operation, all other operations such as exchange is cost free<\/p>\r\n \r\n\r\nLet us apply comparison model for finding lower and upper bounds.\r\n\r\n \r\n\r\n \r\n\r\nFinding Maximum in an array<\/strong>\r\n\r\n \r\n

      Given an array, the problem is to find maximum element. One can easily find that, the upper bound is n-1 as at most n-1 comparisons are sufficient to find maximum of n elements. Similarly, the lower bound is n-1 as n-1 comparisons are necessary in worst case to find the maximum of n elements. In short, finding the maximum element in an array is a linear algorithm of complexity O(n).<\/p>\r\n \r\n\r\n \r\n\r\nFinding the second largest element in Array<\/strong>\r\n\r\n \r\n

      Finding the second largest element in an array is an interesting problem. This problem could be solved by sorting the elements using a sorting algorithm. This requires a time of O(n log n). Instead, a better algorithm can be found. This is done by a method called tournament method and is shown Fig. 1 for 8 elements.<\/p>\r\n \r\n\r\n\"\"\r\n

      \r\n\r\nHow many comparisons are required?\r\n\r\n \r\n

      Finding upper bound is easy as n-1 comparisons are sufficient to find maximum of n elements. What about lower bound? It can be recollected from divide and conquer discussion for this problem, 2n-3 comparisons are necessary in worst case to find the maximum of n elements. For example, the largest element requires n-1 comparison, the next largest of the remainder requires n-2 comparisons. In total, 2n-3 comparisons are required.<\/p>\r\n \r\n\r\n \r\n\r\nLower Bound finding methods:<\/strong>\r\n\r\n \r\n\r\nThere are various methods for finding the lower bound. In this module, two techniques are discussed. They are\r\n\r\n \r\n\r\n1.\u00a0 Trivial lower bounds\r\n\r\n \r\n\r\n2.\u00a0\u00a0\u00a0 Information-theoretic arguments (decision trees)\r\n\r\n \r\n\r\n \r\n\r\nLet us discuss about them now.\r\n\r\n<\/div>\r\n \r\n\r\nTrivial Lowe r Bounds<\/strong>\r\n\r\n \r\n

      Based on counting the number of items that must be processed in input and generated as output [2,3]. This is a very primitive method and can be applied to a small set of problems. For example, consider the problem of finding maximum element in array. It requires n steps or n\/2 comparisons at most. This is the trivial bound.<\/p>\r\n \r\n\r\n \r\n\r\nDecision Tree<\/strong>\r\n\r\n \r\n

      Decision tree is an information theoretic method. It is very popular [1,3,4]. Decision Tree is a convenient model of algorithms involving comparisons in which the internal nodes represent comparisons and the leaves represent outcomes (or input cases).<\/p>\r\nLet us consider a sorting problem of six elements. This is given in Fig. 2.\r\n\r\n \r\n\r\n\"\"\r\n

      In decision tree model, to find the lower bound, we have to find the smallest depth of a binary tree. Based on Fig 2 for six elements, one can easily verify that for \u2018n\u2019 elements, there will be n! distinct permutations and there would be n! leaf nodes in the binary decision tree.<\/p>\r\n \r\n\r\nIn a balanced tree has the smallest depth:\r\n\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\nSummary<\/strong>\r\n\r\n \r\n\r\nOne can conclude from this module that\r\n\r\n \r\n

        \r\n \t
      • Upper bound indicates maximum number of Operations needed.<\/li>\r\n \t
      • Lower bound indicate smallest number of operations required to compute<\/li>\r\n \t
      • Establishing upper and lower bound is must<\/li>\r\n \t
      • Proof techniques are important to establish upper and Lower bounds.<\/li>\r\n<\/ul>\r\n \r\n\r\nReferences:<\/strong>\r\n\r\n \r\n
          \r\n \t
        1. S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/li>\r\n \t
        2. A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\r\n \t
        3. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.<\/li>\r\n \t
        4. K.S.Easwarakumar, Design and Analysis of Algorithms, MCA Text, Anna University.<\/li>\r\n<\/ol>","rendered":"
          \n

          This module 31 focuses on introducing theory of computational complexity. The module discusses how to find limitations of algorithms in terms of upper and lower bounds. The module also discusses the ways of finding lower bound of the algorithms. The objectives of this module are<\/p>\n

           <\/p>\n

          \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the concept of Computational Complexity<\/p>\n

          \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To Understand Upper bound theory<\/p>\n

          \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To Understand Lower Bound Theory<\/p>\n

          \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To know about Proof of Lower Bound Theory<\/p>\n

           <\/p>\n

          Computational Complexity<\/strong><\/p>\n

           <\/p>\n

          There are two types of complexity theory. One is related to algorithm complexity analysis called algorithmic complexity theory and another related to problems called computational complexity theory.<\/p>\n

           <\/p>\n

          Algorithmic complexity theory aims to analyze the algorithms in terms of the size of the problem. In modules 3 and 4, we had discussed about these methods. The size is the length of the input. It can be recollected from module 3 that the size of a number<\/strong> n<\/em> is defined to be the number of binary bits needed to write n. For example,<\/em> Example: b(5) = b(1012) = 3. In other words, the complexity of the algorithm is stated in terms of the size of the algorithm.<\/p>\n

           <\/p>\n

          Asymptotic Analysis <\/strong>refers to the study of an algorithm as the input size reaches a limit and analyzing the behaviour of the algorithms. The asymptotic analysis is also science of approximation where the behaviour of the algorithm is expressed in terms of notations such as big-oh, Big-Omega and Big- Theta.<\/p>\n

           <\/p>\n

          Computational complexity theory is different. Computational complexity aims to determine lower bound on the efficiency of all the algorithms for a given problem and Computational complexity is measured independently of the implementation. In simple words, computational complexity is about the problem and not the algorithm.\u00a0In computational complexity theory, two things are important. One is the upper bound and another is the lower bound of the algorithm. Lower and upper bounds <\/span>defines the limits of the algorithm. Upper bound indicates the worst case performanc e of the algorithm and lower bound indicates the best case performance of the given algorithm.<\/span><\/p>\n<\/div>\n

          \n

           <\/p>\n

          Uppe r bound of the Algorithm<\/strong><\/p>\n

           <\/p>\n

          Upper bound of the algorithm is the pessimistic view of the algorithm. It can be used to indicate worst, average and best case analysis of the algorithm and often expressed as a function. It can be viewed as a proof that the given problem can be solved using at most \u2018n\u2019 operations, even in the worst case.<\/p>\n

           <\/p>\n

          The upper bound for an algorithm is used to indicate the upper or highest growth rate. Normally the algorithm is measured with respect to best, worst and average case analysis. It can be said based on literature [1,2,3] that \u201cthe running time grows at most this much, but it could grow more slowly\u201d.<\/p>\n

           <\/p>\n

          In other words, the cost also is represented as a function. How to determine the upper bound of an algorithm? Let A be the algorithm to be analyzed and if In is set of all possible inputs to Algorithm A and fA (I) is the resource cost of the algorithm when given input I ranges over I<\/em>n<\/em> . Then, the following costs can be defined:<\/p>\n

           <\/p>\n

           <\/p>\n

          worst cost (A) = max I\u00a0 \u00ce I<\/em>n<\/em>\u00a0 fA(I)<\/p>\n

           <\/p>\n

          Best\u00a0 cost (A) = min I \u00ce I<\/em>n<\/em>\u00a0\u00a0 fA(I)<\/p>\n

           <\/p>\n

           <\/p>\n

          One can say the upper bound of the algorithm succinctly using Big-oh notation [4]. It can be described for run time T(n) of the given algorithm as follows: Let T(n) a non-negatively valued function, then T(n) is in set O(\u0192(n)) if there exists two positive constants c and n0 such that T(n)<\/p>\n

           <\/p>\n

          \u2264 c\u0192 (n) for all n > n0. Here, \u00a0\u00a0and .<\/p>\n<\/div>\n

           <\/p>\n

          For example, for towers of Hanoi, the upper bound is is given as f(n) = 2n-1. One can verify that by substituting different values for \u2018n\u2019 and verify it matches with the number of disks movement to move dist from source peg to destination peg. This is shown in table 1.<\/p>\n

           <\/p>\n

          \"\"<\/p>\n

           <\/p>\n

          \n

          From this one can guess, that the upper bound is 2n-1.<\/p>\n

           <\/p>\n

          One can also recollect from modules 3, 4 and 5, we called this as mathematical Induction and using which the upper bound is correctly established.<\/p>\n

           <\/p>\n

           <\/p>\n

          Lower Bound Theory<\/strong><\/p>\n

           <\/p>\n

          Lower bound is for problems and finding it is difficult compared to upper bound of the algorithm. Lower bound is the smallest number of operations necessary to solve a problem over all inputs of size n. In short, it is \u201cAt least this much work to be done\u201d [2,3].<\/p>\n<\/div>\n

           <\/p>\n

          Lower bound is an indication of how hard the algorithm is! It is done for problems and not algorithms. In other words, it is obtained the \u201cbest\u2019 algorithms that is required to solve the given problem. Let M be the model, and if Am is the set of all algorithms for problem P, then the Lower bound on the worst cost of P is given as follows:<\/p>\n

           <\/p>\n

          min A belongs Am { max fA(I)}<\/p>\n

           <\/p>\n

          Some of the examples of the lower bound are given as follows:<\/p>\n

            \n
          1. Number of comparisons needed to find the largest element in a set of n<\/em> numbers<\/li>\n
          2. Number of comparisons needed to sort an array of size n<\/em><\/li>\n
          3. Number of comparisons necessary for searching in a sorted array<\/li>\n
          4. Number of multiplications needed to multiply two n<\/em>-by-n<\/em> matrices<\/li>\n<\/ol>\n

             <\/p>\n

            Lower bound for an algorithm with run time T(n) is given formally as follows:<\/p>\n

             <\/p>\n

             <\/p>\n

            T(n) a non-negatively valued function, T(n) is in set \u03a9(\u0192(n)) if there exists two positive constants c and n0 such that T(n) \u2265 c\u0192(n) for all n > n0.<\/p>\n

             <\/p>\n

            \"\"<\/p>\n

             <\/p>\n

            \n

            Lower bounds can be of two types.<\/p>\n

             <\/p>\n

            \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Worst Case Lower bound<\/p>\n

            \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Average case Lower bound<\/p>\n

             <\/p>\n

             <\/p>\n

            It must be observed that the actual cost is in between Upper and Lower bound and lower bound indicates how optimal the algorithm is! A best scenario is lower bound = upper bound or nearly equal and if not, then better search for solution continues.<\/p>\n

             <\/p>\n

            Let us discuss about sorting problems where these theories can be applied.<\/p>\n

             <\/p>\n

             <\/p>\n

            Sorting proble ms<\/strong><\/p>\n

             <\/p>\n

            There are two models for finding bounds for sorting problems. They are<\/p>\n

              \n
            • \u00a0Exchange Model<\/li>\n
            • Comparison model<\/li>\n<\/ul>\n<\/div>\n

              Let us discuss about them now.<\/p>\n

               <\/p>\n

              Exchange Model<\/strong><\/p>\n

               <\/p>\n

              In exchange model, the input consists of \u2018n\u2019 items and the only operation allowed is exchange at a cost of 1 step [2,3]. All other operations like comparison, examining item is considered as cost free operations. In exchange model, n-1 exchanges are required. Therefore, the upper Bound is n-1 exchanges are sufficient and for lower bound, n-1 Exchanges are necessary in the worst case . In short, n-1 represents the cost required for lower and upper bound.<\/p>\n

               <\/p>\n

              Comparison Model<\/strong><\/p>\n

               <\/p>\n

              In comparison model, the important operation is comparison operations [3]. In this model, the input consists of \u2018n\u2019 items and the only operation allowed is comparison information as yes \/ No. Apart from comparison operation, all other operations such as exchange is cost free<\/p>\n

               <\/p>\n

              Let us apply comparison model for finding lower and upper bounds.<\/p>\n

               <\/p>\n

               <\/p>\n

              Finding Maximum in an array<\/strong><\/p>\n

               <\/p>\n

              Given an array, the problem is to find maximum element. One can easily find that, the upper bound is n-1 as at most n-1 comparisons are sufficient to find maximum of n elements. Similarly, the lower bound is n-1 as n-1 comparisons are necessary in worst case to find the maximum of n elements. In short, finding the maximum element in an array is a linear algorithm of complexity O(n).<\/p>\n

               <\/p>\n

               <\/p>\n

              Finding the second largest element in Array<\/strong><\/p>\n

               <\/p>\n

              Finding the second largest element in an array is an interesting problem. This problem could be solved by sorting the elements using a sorting algorithm. This requires a time of O(n log n). Instead, a better algorithm can be found. This is done by a method called tournament method and is shown Fig. 1 for 8 elements.<\/p>\n

               <\/p>\n

              \"\"<\/p>\n

              \n

              How many comparisons are required?<\/p>\n

               <\/p>\n

              Finding upper bound is easy as n-1 comparisons are sufficient to find maximum of n elements. What about lower bound? It can be recollected from divide and conquer discussion for this problem, 2n-3 comparisons are necessary in worst case to find the maximum of n elements. For example, the largest element requires n-1 comparison, the next largest of the remainder requires n-2 comparisons. In total, 2n-3 comparisons are required.<\/p>\n

               <\/p>\n

               <\/p>\n

              Lower Bound finding methods:<\/strong><\/p>\n

               <\/p>\n

              There are various methods for finding the lower bound. In this module, two techniques are discussed. They are<\/p>\n

               <\/p>\n

              1.\u00a0 Trivial lower bounds<\/p>\n

               <\/p>\n

              2.\u00a0\u00a0\u00a0 Information-theoretic arguments (decision trees)<\/p>\n

               <\/p>\n

               <\/p>\n

              Let us discuss about them now.<\/p>\n<\/div>\n

               <\/p>\n

              Trivial Lowe r Bounds<\/strong><\/p>\n

               <\/p>\n

              Based on counting the number of items that must be processed in input and generated as output [2,3]. This is a very primitive method and can be applied to a small set of problems. For example, consider the problem of finding maximum element in array. It requires n steps or n\/2 comparisons at most. This is the trivial bound.<\/p>\n

               <\/p>\n

               <\/p>\n

              Decision Tree<\/strong><\/p>\n

               <\/p>\n

              Decision tree is an information theoretic method. It is very popular [1,3,4]. Decision Tree is a convenient model of algorithms involving comparisons in which the internal nodes represent comparisons and the leaves represent outcomes (or input cases).<\/p>\n

              Let us consider a sorting problem of six elements. This is given in Fig. 2.<\/p>\n

               <\/p>\n

              \"\"<\/p>\n

              In decision tree model, to find the lower bound, we have to find the smallest depth of a binary tree. Based on Fig 2 for six elements, one can easily verify that for \u2018n\u2019 elements, there will be n! distinct permutations and there would be n! leaf nodes in the binary decision tree.<\/p>\n

               <\/p>\n

              In a balanced tree has the smallest depth:<\/p>\n

               <\/p>\n

               <\/p>\n

              \"\"<\/p>\n

               <\/p>\n

              Summary<\/strong><\/p>\n

               <\/p>\n

              One can conclude from this module that<\/p>\n

               <\/p>\n

                \n
              • Upper bound indicates maximum number of Operations needed.<\/li>\n
              • Lower bound indicate smallest number of operations required to compute<\/li>\n
              • Establishing upper and lower bound is must<\/li>\n
              • Proof techniques are important to establish upper and Lower bounds.<\/li>\n<\/ul>\n

                 <\/p>\n

                References:<\/strong><\/p>\n

                 <\/p>\n

                  \n
                1. S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/li>\n
                2. A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\n
                3. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.<\/li>\n
                4. K.S.Easwarakumar, Design and Analysis of Algorithms, MCA Text, Anna University.<\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":10,"template":"","meta":{"_acf_changed":false,"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["mr-s-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-129","chapter","type-chapter","status-publish","hentry","contributor-mr-s-sridhar"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/129","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":3,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/129\/revisions"}],"predecessor-version":[{"id":137,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/129\/revisions\/137"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/129\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/media?parent=129"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapter-type?post=129"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/contributor?post=129"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/license?post=129"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}