{"id":251754,"date":"2017-02-28T05:59:10","date_gmt":"2017-02-28T12:59:10","guid":{"rendered":"http:\/\/css-tricks.com\/?p=251754"},"modified":"2017-02-28T06:17:46","modified_gmt":"2017-02-28T13:17:46","slug":"computer-science-distilled-chapter-2-complexity","status":"publish","type":"post","link":"https:\/\/css-tricks.com\/computer-science-distilled-chapter-2-complexity\/","title":{"rendered":"Computer Science Distilled, Chapter 2: Complexity"},"content":{"rendered":"<div class=\"explanation\">This is a full chapter excerpt from Wladston Viana Ferreira Filho&#8217;s brand new book <a href=\"http:\/\/amzn.to\/2lEeHZY\" rel=\"noopener\">Computer Science Distilled<\/a> which he has graciously allowed for us to publish here.<\/div>\n<blockquote><p>In almost every computation, a variety of arrangements for the processes is possible. It is essential to choose that arrangement which shall tend to minimize the time necessary for the calculation.<\/p><\/blockquote>\n<p>\u2014Ada Lovelace<\/p>\n<p>How much time does it take to sort 26 shuffled cards? If instead, you had 52 cards, would it take twice as long? How much longer would it take for a thousand decks of cards? The answer is intrinsic to the <strong>method<\/strong> used to sort the cards.<\/p>\n<p>A method is a list of unambiguous instructions for achieving a goal. A method that always requires a finite series of operations is called an <strong>algorithm<\/strong>. For instance, a card-sorting algorithm is a method that will always specify some operations to sort a deck of 26 cards per suit and per rank.<\/p>\n<p>Less operations need less computing power. We like fast solutions, so we monitor the number of operations in our algorithms. Many algorithms require a fast-growing number of operations when the input grows in size. For example, our card-sorting algorithm could take few operations to sort 26 cards, but four times more operations to sort 52 cards!<\/p>\n<p>To avoid bad surprises when our problem size grows, we find the algorithm&#8217;s <strong>time complexity<\/strong>. In this chapter, you&#8217;ll learn to:<\/p>\n<ul>\n<li>Count and interpret <span class=\"ltx_text ltx_font_bold\">time<\/span> complexities<\/li>\n<li>Express their growth with fancy <strong>Big-O<\/strong>&#8216;s<\/li>\n<li>Run away from <strong>exponential<\/strong> algorithms<\/li>\n<li>Make sure you have enough computer <strong>memory<\/strong>.<\/li>\n<\/ul>\n<p>But first, how do we define time complexity?<\/p>\n<p>Time complexity is written <math id=\"Ch2.p8.m1\" class=\"ltx_Math\" alttext=\"T(n)\" display=\"inline\"><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math>. It gives the number of operations the algorithm performs when processing an input of size <math id=\"Ch2.p8.m2\" class=\"ltx_Math\" alttext=\"n\" display=\"inline\"><mi>n<\/mi><\/math>. We also refer to an algorithm's <math id=\"Ch2.p8.m3\" class=\"ltx_Math\" alttext=\"T(n)\" display=\"inline\"><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> as its <strong>running cost<\/strong>. If our card-sorting algorithm follows <math id=\"Ch2.p8.m4\" class=\"ltx_Math\" alttext=\"T(n)=n^{2}\" display=\"inline\"><mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mo>=<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/mrow><\/math>, we can predict how much longer it takes to sort a deck once we double its size: <math id=\"Ch2.p8.m5\" class=\"ltx_Math\" alttext=\"\\frac{T(2n)}{T(n)}=4\" display=\"inline\"><mrow><mfrac><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mrow><mn>2<\/mn><mo>\u2062<\/mo><mi>n<\/mi><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/mfrac><mo>=<\/mo><mn>4<\/mn><\/mrow><\/math>.<\/p>\n<h3>Hope for the best, prepare for the worst<\/h3>\n<p>Isn't it faster to sort a pile of cards that's almost sorted already?<\/p><p>Input size isn't the only characteristic that impacts the number of operations required by an algorithm. When an algorithm can have different values of <math id=\"Ch2.S0.SS1.p1.m1\" class=\"ltx_Math\" alttext=\"T(n)\" display=\"inline\"><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> for the same value of <math id=\"Ch2.S0.SS1.p1.m2\" class=\"ltx_Math\" alttext=\"n\" display=\"inline\"><mi>n<\/mi><\/math>, we resort to cases:<\/p>\n<ul>\n<li><strong>Best Case:<\/strong> when the input requires the minimum number of operations for any input of that size. In sorting, it happens when the input is already sorted.<\/li>\n<li><strong>Worst Case:<\/strong> when the input requires the maximum number of operations for any input of that size. In many sorting algorithms, that\u2019s when the input was given in reverse order.<\/li>\n<li><strong>Average Case:<\/strong> refers to the average number of operations required for typical inputs of that size. For sorting, an input in random order is usually considered.<\/li>\n<\/ul>\n<p>In general, the most important is the worst case. From there, you get a guaranteed baseline you can always count on. When nothing is said about the scenario, the worst case is assumed. Next, we&#8217;ll see how to analyze a worst case scenario, hands on.<\/p>\n<figure id=\"post-251758\" class=\"align-none media-251758\"><img decoding=\"async\" src=\"https:\/\/i0.wp.com\/css-tricks.com\/wp-content\/uploads\/2017\/02\/xkcd_1658.png?ssl=1\" alt=\"\" data-recalc-dims=\"1\" \/><figcaption>Figure 2.1: \u201cEstimating Time\u201d, courtesy of <a href=\"http:\/\/xkcd.com\" rel=\"noopener\">xkcd.com<\/a>.<\/figcaption><\/figure>\n<h3>2.1 Counting Time<\/h3>\n<p>We find the time complexity of an algorithm by counting the number of basic operations it requires for a hypothetical input of size <math id=\"Ch2.S1.p1.m1\" class=\"ltx_Math\" alttext=\"n\" display=\"inline\"><mi>n<\/mi><\/math>. We'll demonstrate it with <strong>Selection Sort<\/strong>, a sorting algorithm that uses a nested loop. An outer <code>for<\/code> loop updates the current position being sorted, and an inner <code>for<\/code> loop selects the item that goes in the current position<sup>1<\/sup>:<\/p>\n<pre><code>function selection_sort(list)\r\n    for current \u2190 1 \u2026 list.length - 1\r\n        smallest \u2190 current\r\n        for i \u2190 current + 1 \u2026 list.length\r\n            if list[i] &lt; list[smallest]\r\n                smallest \u2190 i\r\n        list.swap_items(current, smallest)<\/code><\/pre>\n<p>Let's see what happens with a list of <math id=\"Ch2.S1.p3.m1\" class=\"ltx_Math\" alttext=\"n\" display=\"inline\"><mi>n<\/mi><\/math> items, assuming\r\nthe worst case. The outer loop runs <math id=\"Ch2.S1.p3.m2\" class=\"ltx_Math\" alttext=\"n-1\" display=\"inline\"><mrow><mi>n<\/mi><mo>-<\/mo><mn>1<\/mn><\/mrow><\/math> times and does two\r\noperations per run (one assignment and one swap) totaling <math id=\"Ch2.S1.p3.m3\" class=\"ltx_Math\" alttext=\"2n-2\" display=\"inline\"><mrow><mrow><mn>2<\/mn><mo>\u2062<\/mo><mi>n<\/mi><\/mrow><mo>-<\/mo><mn>2<\/mn><\/mrow><\/math> operations. The inner loop first runs <math id=\"Ch2.S1.p3.m4\" class=\"ltx_Math\" alttext=\"n-1\" display=\"inline\"><mrow><mi>n<\/mi><mo>-<\/mo><mn>1<\/mn><\/mrow><\/math> times, then <math id=\"Ch2.S1.p3.m5\" class=\"ltx_Math\" alttext=\"n-2\" display=\"inline\"><mrow><mi>n<\/mi><mo>-<\/mo><mn>2<\/mn><\/mrow><\/math> times, <math id=\"Ch2.S1.p3.m6\" class=\"ltx_Math\" alttext=\"n-3\" display=\"inline\"><mrow><mi>n<\/mi><mo>-<\/mo><mn>3<\/mn><\/mrow><\/math> times, and so on. We know how to sum these types of sequences<sup>2<\/sup>:\n<table class=\"leave-alone\">\n<tr>\n<td><\/td>\n<td><math id=\"Ch2.Ex1X.m2\" class=\"ltx_Math\" alttext=\"\\displaystyle{\\small\\text{number of inner loop runs}}\\,=\" display=\"inline\"><mrow><mpadded width=\"+1.7pt\"><mtext mathsize=\"90%\">number of inner loop runs<\/mtext><\/mpadded><mo>=<\/mo><mi><\/mi><\/mrow><\/math><\/td>\n<td class=\"ltx_td ltx_align_left ltx_eqn_cell\"><math id=\"Ch2.Ex1X.m3\" class=\"ltx_Math\" alttext=\"\\displaystyle\\overbrace{n-1\\quad\\ \\ \\quad+\\quad\\ \\ \\quad n-2\\quad+\\quad\\cdots+%\n2+1}^{n-1\\ \\text{total runs of the outer loop.}}\" display=\"inline\"><mover><mover accent=\"true\"><mrow><mrow><mi>n<\/mi><mo movablelimits=\"false\">&#8211;<\/mo><mn>1<\/mn><\/mrow><mo movablelimits=\"false\" separator=\"true\">\u2003\u2003\u2003<\/mo><mo movablelimits=\"false\">+<\/mo><mo movablelimits=\"false\" separator=\"true\">\u2003\u2003\u2003<\/mo><mrow><mi>n<\/mi><mo movablelimits=\"false\">&#8211;<\/mo><mn>2<\/mn><\/mrow><mo movablelimits=\"false\" separator=\"true\">\u2003<\/mo><mo movablelimits=\"false\">+<\/mo><mo movablelimits=\"false\" separator=\"true\">\u2003<\/mo><mrow><mi mathvariant=\"normal\">\u22ef<\/mi><mo movablelimits=\"false\">+<\/mo><mn>2<\/mn><mo movablelimits=\"false\">+<\/mo><mn>1<\/mn><\/mrow><\/mrow><mo movablelimits=\"false\">\u23de<\/mo><\/mover><mrow><mi>n<\/mi><mo>&#8211;<\/mo><mrow><mpadded width=\"+5pt\"><mn>1<\/mn><\/mpadded><mo>\u2062<\/mo><mtext>total runs of the outer loop.<\/mtext><\/mrow><\/mrow><\/mover><\/math><\/td>\n<td class=\"ltx_eqn_cell ltx_eqn_center_padright\"><\/td>\n<\/tr>\n<tr>\n<td><\/td>\n<td style=\"text-align: right;\"><math id=\"Ch2.Ex1Xa.m2\" class=\"ltx_Math\" alttext=\"\\displaystyle=\" display=\"inline\"><mo>=<\/mo><\/math><\/td>\n<td><math id=\"Ch2.Ex1Xa.m3\" class=\"ltx_Math\" alttext=\"\\displaystyle\\sum_{i=1}^{n-1}i=\\frac{(n-1)(n)}{2}=\\frac{n^{2}-n}{2}.\" display=\"inline\"><mrow><mrow><mrow><mstyle displaystyle=\"true\"><munderover><mo largeop=\"true\" movablelimits=\"false\" symmetric=\"true\">\u2211<\/mo><mrow><mi>i<\/mi><mo>=<\/mo><mn>1<\/mn><\/mrow><mrow><mi>n<\/mi><mo>&#8211;<\/mo><mn>1<\/mn><\/mrow><\/munderover><\/mstyle><mi>i<\/mi><\/mrow><mo>=<\/mo><mstyle displaystyle=\"true\"><mfrac><mrow><mrow><mo stretchy=\"false\">(<\/mo><mrow><mi>n<\/mi><mo>&#8211;<\/mo><mn>1<\/mn><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mn>2<\/mn><\/mfrac><\/mstyle><mo>=<\/mo><mstyle displaystyle=\"true\"><mfrac><mrow><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo>&#8211;<\/mo><mi>n<\/mi><\/mrow><mn>2<\/mn><\/mfrac><\/mstyle><\/mrow><mo>.<\/mo><\/mrow><\/math><\/td>\n<td><\/td>\n<\/tr>\n<\/table>\n<p>In the worst case, the <span class=\"ltx_text ltx_font_typewriter\">if<\/span> condition is always met. This means the inner loop does one comparison and one assignment <math id=\"Ch2.S1.p5.m1\" class=\"ltx_Math\" alttext=\"(n^{2}-n)\/2\" display=\"inline\"><mrow><mrow><mo stretchy=\"false\">(<\/mo><mrow><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo>-<\/mo><mi>n<\/mi><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><mo>\/<\/mo><mn>2<\/mn><\/mrow><\/math> times, hence <math id=\"Ch2.S1.p5.m2\" class=\"ltx_Math\" alttext=\"n^{2}-n\" display=\"inline\"><mrow><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo>-<\/mo><mi>n<\/mi><\/mrow><\/math> operations. In total, the algorithm costs <math id=\"Ch2.S1.p5.m3\" class=\"ltx_Math\" alttext=\"2n-2\" display=\"inline\"><mrow><mrow><mn>2<\/mn><mo>\u2062<\/mo><mi>n<\/mi><\/mrow><mo>-<\/mo><mn>2<\/mn><\/mrow><\/math> operations for the outer loop, plus <math id=\"Ch2.S1.p5.m4\" class=\"ltx_Math\" alttext=\"n^{2}-n\" display=\"inline\"><mrow><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo>-<\/mo><mi>n<\/mi><\/mrow><\/math> operations for the inner loop. We thus get the time complexity:<\/p>\n<table class=\"leave-alone\">\n<tr>\n<td><\/td>\n<td><math id=\"Ch2.Ex2.m1\" class=\"ltx_Math\" alttext=\"T(n)=n^{2}+n-2.\" display=\"block\"><mrow><mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mo>=<\/mo><mrow><mrow><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo>+<\/mo><mi>n<\/mi><\/mrow><mo>&#8211;<\/mo><mn>2<\/mn><\/mrow><\/mrow><mo>.<\/mo><\/mrow><\/math><\/td>\n<td><\/td>\n<\/tr>\n<\/table>\n<p>Now what? If our list size was <math id=\"Ch2.S1.p7.m1\" class=\"ltx_Math\" alttext=\"n=8\" display=\"inline\"><mrow><mi>n<\/mi><mo>=<\/mo><mn>8<\/mn><\/mrow><\/math> and we double it, the\r\nsorting time will be multiplied by:<\/p>\n<table class=\"leave-alone\">\n<tr>\n<td><\/td>\n<td><math id=\"Ch2.Ex3.m1\" class=\"ltx_Math\" alttext=\"\\frac{T(16)}{T(8)}=\\frac{16^{2}+16-2}{8^{2}+8-2}\\approx 3.86.\" display=\"block\"><mrow><mrow><mfrac><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mn>16<\/mn><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mn>8<\/mn><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/mfrac><mo>=<\/mo><mfrac><mrow><mrow><msup><mn>16<\/mn><mn>2<\/mn><\/msup><mo>+<\/mo><mn>16<\/mn><\/mrow><mo>&#8211;<\/mo><mn>2<\/mn><\/mrow><mrow><mrow><msup><mn>8<\/mn><mn>2<\/mn><\/msup><mo>+<\/mo><mn>8<\/mn><\/mrow><mo>&#8211;<\/mo><mn>2<\/mn><\/mrow><\/mfrac><mo>\u2248<\/mo><mn>3.86<\/mn><\/mrow><mo>.<\/mo><\/mrow><\/math><\/td>\n<td><\/td>\n<\/tr>\n<\/table>\n<p>If we double it again we will multiply time by <math id=\"Ch2.S1.p9.m1\" class=\"ltx_Math\" alttext=\"3.90\" display=\"inline\"><mn>3.90<\/mn><\/math>. Double it over and over and find <math id=\"Ch2.S1.p9.m2\" class=\"ltx_Math\" alttext=\"3.94\" display=\"inline\"><mn>3.94<\/mn><\/math>, <math id=\"Ch2.S1.p9.m3\" class=\"ltx_Math\" alttext=\"3.97\" display=\"inline\"><mn>3.97<\/mn><\/math>, <math id=\"Ch2.S1.p9.m4\" class=\"ltx_Math\" alttext=\"3.98\" display=\"inline\"><mn>3.98<\/mn><\/math>. Notice how this gets closer and closer to 4? This means it would take four times as long to sort two million items than to sort one million items.<\/p>\n<h4>2.1.1 Understanding Growth<\/h4>\n<p>Say the input size of an algorithm is very large, and we increase it even more. To predict how the execution time will grow, we don't need to know all terms of <math id=\"Ch2.S1.SS1.p1.m1\" class=\"ltx_Math\" alttext=\"T(n)\" display=\"inline\"><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math>. We can approximate <math id=\"Ch2.S1.SS1.p1.m2\" class=\"ltx_Math\" alttext=\"T(n)\" display=\"inline\"><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> by its fastest-growing term, called the <strong>dominant term<\/strong>.<\/p>\n<blockquote><p><strong>The Index Card Problem:<\/strong> Yesterday, you knocked over one box of index cards. It took you two hours of Selection Sort to fix it. Today, you spilled ten boxes. How much time will you need to arrange the cards back in?<\/p><\/blockquote>\n<p>We've seen Selection Sort follows <math id=\"Ch2.S1.SS1.p3.m1\" class=\"ltx_Math\" alttext=\"T(n)=n^{2}+n-2\" display=\"inline\"><mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mo>=<\/mo><mrow><mrow><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo>+<\/mo><mi>n<\/mi><\/mrow><mo>-<\/mo><mn>2<\/mn><\/mrow><\/mrow><\/math>. The fastest-growing term is <math id=\"Ch2.S1.SS1.p3.m2\" class=\"ltx_Math\" alttext=\"n^{2}\" display=\"inline\"><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/math>,\r\ntherefore we can write <math id=\"Ch2.S1.SS1.p3.m3\" class=\"ltx_Math\" alttext=\"T(n)\\approx n^{2}\" display=\"inline\"><mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mo>\u2248<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/mrow><\/math>. Assuming there are <math id=\"Ch2.S1.SS1.p3.m4\" class=\"ltx_Math\" alttext=\"n\" display=\"inline\"><mi>n<\/mi><\/math> cards per box, we find:<\/p>\n<table class=\"leave-alone\">\n<tr>\n<td><\/td>\n<td class=\"ltx_eqn_cell ltx_align_center\"><math id=\"Ch2.Ex4.m1\" class=\"ltx_Math\" alttext=\"\\frac{T(10n)}{T(n)}\\approx\\frac{{(10n)}^{2}}{n^{2}}=100.\" display=\"block\"><mrow><mrow><mfrac><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mrow><mn>10<\/mn><mo>\u2062<\/mo><mi>n<\/mi><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/mfrac><mo>\u2248<\/mo><mfrac><msup><mrow><mo stretchy=\"false\">(<\/mo><mrow><mn>10<\/mn><mo>\u2062<\/mo><mi>n<\/mi><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><mn>2<\/mn><\/msup><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/mfrac><mo>=<\/mo><mn>100<\/mn><\/mrow><mo>.<\/mo><\/mrow><\/math><\/td>\n<td><\/td>\n<\/tr>\n<\/table>\n<p>It will take you approximately <math id=\"Ch2.S1.SS1.p5.m1\" class=\"ltx_Math\" alttext=\"(100\\times 2)\\text{hours}=200\" display=\"inline\"><mrow><mrow><mrow><mo stretchy=\"false\">(<\/mo><mrow><mn>100<\/mn><mo>\u00d7<\/mo><mn>2<\/mn><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><mo>\u2062<\/mo><mtext>hours<\/mtext><\/mrow><mo>=<\/mo><mn>200<\/mn><\/mrow><\/math> hours! What if we had used a different sorting method? For example, there\u2019s one called \"Bubble Sort\" whose time complexity is <math id=\"Ch2.S1.SS1.p5.m2\" class=\"ltx_Math\" alttext=\"T(n)=0.5n^{2}+0.5n\" display=\"inline\"><mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mo>=<\/mo><mrow><mrow><mn>0.5<\/mn><mo>\u2062<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/mrow><mo>+<\/mo><mrow><mn>0.5<\/mn><mo>\u2062<\/mo><mi>n<\/mi><\/mrow><\/mrow><\/mrow><\/math>. The fastest-growing term then gives <math id=\"Ch2.S1.SS1.p5.m3\" class=\"ltx_Math\" alttext=\"T(n)\\approx 0.5n^{2}\" display=\"inline\"><mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mo>\u2248<\/mo><mrow><mn>0.5<\/mn><mo>\u2062<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/mrow><\/mrow><\/math>, hence:<\/p>\n<table class=\"leave-alone\">\n<tr>\n<td><\/td>\n<td><math id=\"Ch2.Ex5.m1\" class=\"ltx_Math\" alttext=\"\\frac{T(10n)}{T(n)}\\approx\\frac{0.5\\times{(10n)}^{2}}{0.5\\times n^{2}}=100.\" display=\"block\"><mrow><mrow><mfrac><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mrow><mn>10<\/mn><mo>\u2062<\/mo><mi>n<\/mi><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/mfrac><mo>\u2248<\/mo><mfrac><mrow><mn>0.5<\/mn><mo>\u00d7<\/mo><msup><mrow><mo stretchy=\"false\">(<\/mo><mrow><mn>10<\/mn><mo>\u2062<\/mo><mi>n<\/mi><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><mn>2<\/mn><\/msup><\/mrow><mrow><mn>0.5<\/mn><mo>\u00d7<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/mrow><\/mfrac><mo>=<\/mo><mn>100<\/mn><\/mrow><mo>.<\/mo><\/mrow><\/math><\/td>\n<td><\/td>\n<\/tr>\n<\/table>\n<figure id=\"post-251834\" class=\"align-none media-251834\"><img decoding=\"async\" src=\"https:\/\/css-tricks.com\/wp-content\/uploads\/2017\/02\/quad_growth.svg\" alt=\"\" \/><figcaption>Figure\u00a02.2: Zooming out <math id=\"Ch2.F2.m5\" class=\"ltx_Math\" alttext=\"n^{2}\" display=\"inline\"><msup><mi mathcolor=\"#3B3B3B\">n<\/mi><mn mathcolor=\"#3B3B3B\">2<\/mn><\/msup><\/math><span class=\"ltx_text\" style=\"color:#3B3B3B;\">,\u2002<\/span> <math id=\"Ch2.F2.m6\" class=\"ltx_Math\" alttext=\"n^{2}+n-2\" display=\"inline\"><mrow><mrow><msup><mi mathcolor=\"#0596CC\">n<\/mi><mn mathcolor=\"#0596CC\">2<\/mn><\/msup><mo mathcolor=\"#0596CC\">+<\/mo><mi mathcolor=\"#0596CC\">n<\/mi><\/mrow><mo mathcolor=\"#0596CC\">-<\/mo><mn mathcolor=\"#0596CC\">2<\/mn><\/mrow><\/math><span class=\"ltx_text\" style=\"color:#0596CC;\">,\u2002<\/span> and\r\n\u2002<math id=\"Ch2.F2.m7\" class=\"ltx_Math\" alttext=\"0.5n^{2}+0.5n\" display=\"inline\"><mrow><mrow><mn mathcolor=\"#D9541A\">0.5<\/mn><mo mathcolor=\"#D9541A\">\u2062<\/mo><msup><mi mathcolor=\"#D9541A\">n<\/mi><mn mathcolor=\"#D9541A\">2<\/mn><\/msup><\/mrow><mo mathcolor=\"#D9541A\">+<\/mo><mrow><mn mathcolor=\"#D9541A\">0.5<\/mn><mo mathcolor=\"#D9541A\">\u2062<\/mo><mi mathcolor=\"#D9541A\">n<\/mi><\/mrow><\/mrow><\/math><span class=\"ltx_text\" style=\"color:#D9541A;\">,\u2002<\/span> as <math id=\"Ch2.F2.m8\" class=\"ltx_Math\" alttext=\"n\" display=\"inline\"><mi>n<\/mi><\/math> gets larger and larger.<\/figcaption><\/figure>\n<p>The <math id=\"Ch2.S1.SS1.p7.m1\" class=\"ltx_Math\" alttext=\"0.5\" display=\"inline\"><mn>0.5<\/mn><\/math> coefficient cancels itself out! The idea that <math id=\"Ch2.S1.SS1.p7.m2\" class=\"ltx_Math\" alttext=\"n^{2}-n-2\" display=\"inline\"><mrow><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo>-<\/mo><mi>n<\/mi><mo>-<\/mo><mn>2<\/mn><\/mrow><\/math> and <math id=\"Ch2.S1.SS1.p7.m3\" class=\"ltx_Math\" alttext=\"0.5n^{2}+0.5n\" display=\"inline\"><mrow><mrow><mn>0.5<\/mn><mo>\u2062<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/mrow><mo>+<\/mo><mrow><mn>0.5<\/mn><mo>\u2062<\/mo><mi>n<\/mi><\/mrow><\/mrow><\/math> both grow like <math id=\"Ch2.S1.SS1.p7.m4\" class=\"ltx_Math\" alttext=\"n^{2}\" display=\"inline\"><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/math> isn't easy to get. How does the fastest-growing term of a function ignore all other numbers and dominate growth? Let\u2019s try to visually understand this.<\/p>\n<p>In Figure 2.2, the two time complexities we've seen are compared to <math id=\"Ch2.S1.SS1.p8.m1\" class=\"ltx_Math\" alttext=\"n^{2}\" display=\"inline\"><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/math> at different zoom levels. As we plot them for larger and larger values of <math id=\"Ch2.S1.SS1.p8.m2\" class=\"ltx_Math\" alttext=\"n\" display=\"inline\"><mi>n<\/mi><\/math>, their curves seem to get closer and closer. Actually, you can plug any numbers into the bullets of <math id=\"Ch2.S1.SS1.p8.m3\" class=\"ltx_Math\" alttext=\"T(n)=\\mathord{\\bullet}\\enskip n^{2}+\\mathord{\\bullet}\\enskip n+\\mathord{\\bullet}\" display=\"inline\"><mrow><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mo>=<\/mo><mrow><mrow><mpadded width=\"+5pt\"><mi mathvariant=\"normal\">\u2219<\/mi><\/mpadded><mo>\u2062<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/mrow><mo>+<\/mo><mrow><mpadded width=\"+5pt\"><mi mathvariant=\"normal\">\u2219<\/mi><\/mpadded><mo>\u2062<\/mo><mi>n<\/mi><\/mrow><mo>+<\/mo><mi mathvariant=\"normal\">\u2219<\/mi><\/mrow><\/mrow><\/math>, and it will still grow like <math id=\"Ch2.S1.SS1.p8.m4\" class=\"ltx_Math\" alttext=\"n^{2}\" display=\"inline\"><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/math>.<\/p>\n<p>Remember, this effect of curves getting closer works if the fastest-growing term is the same. The plot of a function with a linear growth (<math id=\"Ch2.S1.SS1.p9.m1\" class=\"ltx_Math\" alttext=\"n\" display=\"inline\"><mi>n<\/mi><\/math>) never gets closer and closer to one with a quadratic growth (<math id=\"Ch2.S1.SS1.p9.m2\" class=\"ltx_Math\" alttext=\"n^{2}\" display=\"inline\"><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/math>), which in turn never gets closer and closer to one having a cubic growth (<math id=\"Ch2.S1.SS1.p9.m3\" class=\"ltx_Math\" alttext=\"n^{3}\" display=\"inline\"><msup><mi>n<\/mi><mn>3<\/mn><\/msup><\/math>).<\/p>\n<p>That&#8217;s why with very big inputs, algorithms with a quadratically growing cost perform a lot worse than algorithms with a linear cost. However, they perform a lot better than those with a cubic cost. If you\u2019ve understood this, the next section will be easy: we will just learn the fancy notation coders use to express this.<\/p>\n<h3>2.2 The Big-O Notation<\/h3>\n<p>There's a special notation to refer to classes of growth: the <span class=\"ltx_text ltx_font_bold\">Big-O notation<\/span>. A function with a fastest-growing term of <math id=\"Ch2.S2.p1.m1\" class=\"ltx_Math\" alttext=\"2^{n}\" display=\"inline\"><msup><mn>2<\/mn><mi>n<\/mi><\/msup><\/math> <em class=\"ltx_emph\">or weaker<\/em> is <math id=\"Ch2.S2.p1.m2\" class=\"ltx_Math\" alttext=\"O(2^{n})\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><msup><mn>2<\/mn><mi>n<\/mi><\/msup><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math>; one with a quadratic <em class=\"ltx_emph\">or weaker<\/em> growth is <math id=\"Ch2.S2.p1.m3\" class=\"ltx_Math\" alttext=\"O(n^{2})\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math>; growing linearly <em class=\"ltx_emph\">or less<\/em>, <math id=\"Ch2.S2.p1.m4\" class=\"ltx_Math\" alttext=\"O(n)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math>, and so on. The notation is used for expressing the dominant term of algorithms' cost functions in the worst case\u2014that's the standard way of expressing time complexity<sup>3<\/sup>.<\/p>\n<figure id=\"post-251835\" class=\"align-none media-251835\"><img decoding=\"async\" src=\"https:\/\/css-tricks.com\/wp-content\/uploads\/2017\/02\/growth_curves.svg\" alt=\"\" \/><figcaption>Figure\u00a02.3: Different orders of growth often seen inside <math id=\"Ch2.F3.m2\" class=\"ltx_Math\" alttext=\"O\" display=\"inline\"><mi>O<\/mi><\/math>.<\/figcaption><\/figure>\n<p>Both Selection Sort and Bubble Sort are <math id=\"Ch2.S2.p2.m1\" class=\"ltx_Math\" alttext=\"O(n^{2})\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math>, but we'll soon discover <math id=\"Ch2.S2.p2.m2\" class=\"ltx_Math\" alttext=\"O(n\\log n)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mrow><mi>n<\/mi><mo>\u2062<\/mo><mrow><mi>log<\/mi><mo>\u2061<\/mo><mi>n<\/mi><\/mrow><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> algorithms that do the same job. With our <math id=\"Ch2.S2.p2.m3\" class=\"ltx_Math\" alttext=\"O(n^{2})\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> algorithms, 10<math id=\"Ch2.S2.p2.m4\" class=\"ltx_Math\" alttext=\"\\times\" display=\"inline\"><mo>\u00d7<\/mo><\/math> the input size resulted in 100<math id=\"Ch2.S2.p2.m5\" class=\"ltx_Math\" alttext=\"\\times\" display=\"inline\"><mo>\u00d7<\/mo><\/math> the running cost. Using a <math id=\"Ch2.S2.p2.m6\" class=\"ltx_Math\" alttext=\"O(n\\log n)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mrow><mi>n<\/mi><mo>\u2062<\/mo><mrow><mi>log<\/mi><mo>\u2061<\/mo><mi>n<\/mi><\/mrow><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> algorithm, 10<math id=\"Ch2.S2.p2.m7\" class=\"ltx_Math\" alttext=\"\\times\" display=\"inline\"><mo>\u00d7<\/mo><\/math> the input size results in only <math id=\"Ch2.S2.p2.m8\" class=\"ltx_Math\" alttext=\"10\\log 10\\approx 34\\mathord{\\times}\" display=\"inline\"><mrow><mrow><mn>10<\/mn><mo>\u2062<\/mo><mrow><mi>log<\/mi><mo>\u2061<\/mo><mn>10<\/mn><\/mrow><\/mrow><mo>\u2248<\/mo><mrow><mn>34<\/mn><mo>\u2062<\/mo><mi mathvariant=\"normal\">\u00d7<\/mi><\/mrow><\/mrow><\/math> the running cost.<\/p>\n<p>When <math id=\"Ch2.S2.p3.m1\" class=\"ltx_Math\" alttext=\"n\" display=\"inline\"><mi>n<\/mi><\/math> is a million, <math id=\"Ch2.S2.p3.m2\" class=\"ltx_Math\" alttext=\"n^{2}\" display=\"inline\"><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/math> is a trillion, whereas <math id=\"Ch2.S2.p3.m3\" class=\"ltx_Math\" alttext=\"n\\log n\" display=\"inline\"><mrow><mi>n<\/mi><mo>\u2062<\/mo><mrow><mi>log<\/mi><mo>\u2061<\/mo><mi>n<\/mi><\/mrow><\/mrow><\/math> is just a few million. Years running a quadratic algorithm on a large input could be equivalent to minutes if a <math id=\"Ch2.S2.p3.m4\" class=\"ltx_Math\" alttext=\"O(n\\log n)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mrow><mi>n<\/mi><mo>\u2062<\/mo><mrow><mi>log<\/mi><mo>\u2061<\/mo><mi>n<\/mi><\/mrow><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> algorithm was used. That\u2019s why you need time complexity analysis when you design systems that handle very large inputs.<\/p>\n<p>When designing a computational system, it&#8217;s important to anticipate the most frequent operations. Then you can compare the Big-O costs of different algorithms that do these operations<sup>4<\/sup>. Also, most algorithms only work with specific input structures. If you choose your algorithms in advance, you can structure your input data accordingly.<\/p>\n<p>Some algorithms always run for a constant duration regardless of input size\u2014they're <math id=\"Ch2.S2.p5.m1\" class=\"ltx_Math\" alttext=\"O(1)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mn>1<\/mn><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math>. For example, checking if a number is odd or even: we see if its last digit is odd and <em class=\"ltx_emph\">boom<\/em>, problem\r\nsolved. No matter how big the number. We'll see more <math id=\"Ch2.S2.p5.m2\" class=\"ltx_Math\" alttext=\"O(1)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mn>1<\/mn><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> algorithms in the next chapters. They're amazing, but first let's see which algorithms are <em>not<\/em> amazing.<\/p>\n<h3>2.3 Exponentials<\/h3>\n<p>We say <math id=\"Ch2.S3.p1.m1\" class=\"ltx_Math\" alttext=\"O(2^{n})\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><msup><mn>2<\/mn><mi>n<\/mi><\/msup><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> algorithms are <span class=\"ltx_text ltx_font_bold\">exponential time<\/span>. From the graph of growth orders (Figure 2.3), it doesn't seem the quadratic <math id=\"Ch2.S3.p1.m2\" class=\"ltx_Math\" alttext=\"n^{2}\" display=\"inline\"><msup><mi>n<\/mi><mn>2<\/mn><\/msup><\/math> and the exponential <math id=\"Ch2.S3.p1.m3\" class=\"ltx_Math\" alttext=\"2^{n}\" display=\"inline\"><msup><mn>2<\/mn><mi>n<\/mi><\/msup><\/math> are much different. Zooming out the graph, it's obvious the exponential growth brutally dominates the quadratic one:<\/p>\n<figure id=\"post-251836\" class=\"align-none media-251836\"><img decoding=\"async\" src=\"https:\/\/css-tricks.com\/wp-content\/uploads\/2017\/02\/growth_curves_2.svg\" alt=\"\" \/><figcaption>Figure 2.4: Different orders of growth, zoomed out. The linear and logarithmic curves grow so little they aren&#8217;t visible anymore.<\/figcaption><\/figure>\n<p>Exponential time grows so much, we consider these algorithms &#8220;not runnable&#8221;. They run for very few input types, and require huge amounts of computing power if inputs aren&#8217;t tiny. Optimizing every aspect of the code or using supercomputers doesn&#8217;t help. The crushing exponential always dominates growth and keeps these algorithms unviable.<\/p>\n<p>To illustrate the explosiveness of exponential growth, let's zoom out the graph even more and change the numbers (Figure 2.5). The exponential was reduced in power (from <math id=\"Ch2.S3.p3.m1\" class=\"ltx_Math\" alttext=\"2\" display=\"inline\"><mn>2<\/mn><\/math> to <math id=\"Ch2.S3.p3.m2\" class=\"ltx_Math\" alttext=\"1.5\" display=\"inline\"><mn>1.5<\/mn><\/math>) and had its growth divided by a thousand. The polynomial had its exponent increased (from <math id=\"Ch2.S3.p3.m3\" class=\"ltx_Math\" alttext=\"2\" display=\"inline\"><mn>2<\/mn><\/math> to <math id=\"Ch2.S3.p3.m4\" class=\"ltx_Math\" alttext=\"3\" display=\"inline\"><mn>3<\/mn><\/math>) and its growth multiplied by a thousand.<\/p>\n<figure id=\"post-251837\" class=\"align-none media-251837\"><img decoding=\"async\" src=\"https:\/\/css-tricks.com\/wp-content\/uploads\/2017\/02\/growth_curves_3.svg\" alt=\"\" \/><figcaption>Figure\u00a02.5: No exponential can be beaten by a polynomial. At this zoom level, even the <math id=\"Ch2.F5.m2\" class=\"ltx_Math\" alttext=\"n\\log n\" display=\"inline\"><mrow><mi>n<\/mi><mo>\u2062<\/mo><mrow><mi>log<\/mi><mo>\u2061<\/mo><mi>n<\/mi><\/mrow><\/mrow><\/math> curve grows too little to be visible.<\/figure>\n<p>Some algorithms are even worse than exponential time algorithms. It's the case of <span class=\"ltx_text ltx_font_bold\">factorial time<\/span> algorithms, whose time complexities are <math id=\"Ch2.S3.p4.m1\" class=\"ltx_Math\" alttext=\"O(n!)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mrow><mi>n<\/mi><mo lspace=\"0pt\" rspace=\"3.5pt\">!<\/mo><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math>. Exponential and factorial time algorithms are horrible, but we need them for the hardest computational problems: the famous <span class=\"ltx_text ltx_font_bold\">NP-complete<\/span> problems. We will see important examples of NP-complete problems in the next chapter. For now, remember this: the first person to find a non-exponential algorithm to a NP-complete problem gets a million dollars<sup>5<\/sup> from the Clay Mathematics Institute.<\/p>\n<p>It&#8217;s important to recognize the class of problem you&#8217;re dealing with. If it&#8217;s known to be NP-complete, trying to find an optimal solution is fighting the impossible. Unless you\u2019re shooting for that million dollars.<\/p>\n<h3>2.4 Counting Memory<\/h3>\n<p>Even if we could perform operations infinitely fast, there would still be a limit to our computing power. During execution, algorithms need working storage to keep track of their ongoing calculations. This consumes <strong>computer memory<\/strong>, which is not infinite.<\/p>\n<p>The measure for the working storage an algorithm needs is called <strong>space complexity<\/strong>. Space complexity analysis is similar to time complexity analysis. The difference is that we count computer memory, and not computing operations. We observe how space complexity evolves when the algorithm&#8217;s input size grows, just as we do for time complexity.<\/p>\n<p>For example, Selection Sort just needs working storage for a fixed set of variables. The number of variables does not depend on the input size. Therefore, we say Selection Sort's space complexity is <math id=\"Ch2.S4.p3.m1\" class=\"ltx_Math\" alttext=\"O(1)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mn>1<\/mn><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math>: no matter what the input size, it requires the same amount of computer memory for working storage.<\/p>\n<p>However, many other algorithms need working storage that grows with input size. Sometimes, it's impossible to meet an algorithm\u2019s memory requirements. You won't find an appropriate sorting algorithm with <math id=\"Ch2.S4.p4.m1\" class=\"ltx_Math\" alttext=\"O(n\\log n)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mrow><mi>n<\/mi><mo>\u2062<\/mo><mrow><mi>log<\/mi><mo>\u2061<\/mo><mi>n<\/mi><\/mrow><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> time complexity <em class=\"ltx_emph\">and<\/em> <math id=\"Ch2.S4.p4.m2\" class=\"ltx_Math\" alttext=\"O(1)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mn>1<\/mn><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> space complexity. Computer memory limitations sometimes force a tradeoff. With low memory, you\u2019ll probably need an algorithm with slow <math id=\"Ch2.S4.p4.m3\" class=\"ltx_Math\" alttext=\"O(n^{2})\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><msup><mi>n<\/mi><mn>2<\/mn><\/msup><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> time complexity because it has <math id=\"Ch2.S4.p4.m4\" class=\"ltx_Math\" alttext=\"O(1)\" display=\"inline\"><mrow><mi>O<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mn>1<\/mn><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math>\r\nspace complexity.<\/p>\n<h3>Conclusion<\/h3>\n<p>In this chapter, we learned algorithms can have different types of voracity for consuming computing time and computer memory. We\u2019ve seen how to assess it with time and space complexity analysis. We learned to calculate time complexity by finding the <em class=\"ltx_emph\">exact<\/em> <math id=\"Ch2.Sx1.p1.m1\" class=\"ltx_Math\" alttext=\"T(n)\" display=\"inline\"><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> function, the number of operations performed by an algorithm.<\/p>\n<p>We've seen how to express time complexity using the Big-O notation (<math id=\"Ch2.Sx1.p2.m1\" class=\"ltx_Math\" alttext=\"O\" display=\"inline\"><mi>O<\/mi><\/math>). Throughout this book, we'll perform simple time complexity analysis of algorithms using this notation. Many times, calculating <math id=\"Ch2.Sx1.p2.m2\" class=\"ltx_Math\" alttext=\"T(n)\" display=\"inline\"><mrow><mi>T<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><\/math> is not necessary for inferring the Big-O complexity of an algorithm.<\/p>\n<p>We&#8217;ve seen the cost of running exponential algorithms explode in a way that makes these algorithms not runnable for big inputs. And we learned how to answer these questions:<\/p>\n<ul>\n<li>Given different algorithms, do they have a significant difference in terms of operations required to run?<\/li>\n<li>Multiplying the input size by a constant, what happens with the time an algorithm takes to run?<\/li>\n<li>Would an algorithm perform a reasonable number of operations once the size of the input grows?<\/li>\n<li>If an algorithm is too slow for running on an input of a given size, would optimizing the algorithm, or using a supercomputer help?<\/li>\n<\/ul>\n<hr>\n<p><sup>1<\/sup>: To understand an new algorithm, run it on paper with a small sample input.<\/p>\n<p><sup>2<\/sup>: In the previous chapter, we showed <math id=\"Ch2.S1.p3.m7\" class=\"ltx_Math\" alttext=\"\\sum_{i=1}^{n}i=n(n+1)\/2\" display=\"inline\"><mrow><mrow><msubsup><mo largeop=\"true\" symmetric=\"true\">\u2211<\/mo><mrow><mi>i<\/mi><mo>=<\/mo><mn>1<\/mn><\/mrow><mi>n<\/mi><\/msubsup><mi>i<\/mi><\/mrow><mo>=<\/mo><mrow><mrow><mi>n<\/mi><mo>\u2062<\/mo><mrow><mo stretchy=\"false\">(<\/mo><mrow><mi>n<\/mi><mo>+<\/mo><mn>1<\/mn><\/mrow><mo stretchy=\"false\">)<\/mo><\/mrow><\/mrow><mo>\/<\/mo><mn>2<\/mn><\/mrow><\/mrow><\/math>.<\/p>\n<p><sup>3<\/sup>: We say <em>&#8216;oh&#8217;<\/em>, e.g., &#8220;that sorting algorithm is <em>oh-n-squared<\/em>&#8220;.<\/p>\n<p><sup>4<\/sup>: For the Big-O complexities of most algorithms that do common tasks, see <a href=\"http:\/\/code.energy\/bigo\" rel=\"noopener\">http:\/\/code.energy\/bigo<\/a><\/p>\n<p><sup>5<\/sup>: It has been proven a non-exponential algorithm for <em class=\"ltx_emph\">any<\/em> NP-complete problem could be generalized to <em class=\"ltx_emph\">all<\/em> NP-complete problems. Since we don&#8217;t know if such an algorithm exists, you also get a million dollars if you prove an NP-complete problem cannot be solved by non-exponential algorithms!<\/p>\n<hr>\n<figure id=\"post-251767\" class=\"align-none media-251767\"><img decoding=\"async\" src=\"https:\/\/i0.wp.com\/css-tricks.com\/wp-content\/uploads\/2017\/02\/csd.jpeg?ssl=1\" alt=\"\" data-recalc-dims=\"1\" \/><\/figure>\n<p><em>Computer Science Distilled: Learn the Art of Solving Computational Problems<\/em> by Wladston Viana Ferreira Filho is <a href=\"http:\/\/amzn.to\/2mlMhnz\" rel=\"noopener\">available on Amazon<\/a> now. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>This is a full chapter excerpt from Wladston Viana Ferreira Filho&#8217;s brand new book <a href=\"http:\/\/amzn.to\/2lEeHZY\">Computer Science Distilled<\/a> which he has graciously allowed for us to publish here.<\/p>\n<blockquote><p>In almost every computation, a variety of arrangements for the processes is possible. It is essential to choose that arrangement which shall tend to minimize the time necessary for the calculation. \u2014Ada Lovelace<\/p><\/blockquote>\n","protected":false},"author":247919,"featured_media":251767,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_bbp_topic_count":0,"_bbp_reply_count":0,"_bbp_total_topic_count":0,"_bbp_total_reply_count":0,"_bbp_voice_count":0,"_bbp_anonymous_reply_count":0,"_bbp_topic_count_hidden":0,"_bbp_reply_count_hidden":0,"_bbp_forum_subforum_count":0,"sig_custom_text":"","sig_image_type":"featured-image","sig_custom_image":0,"sig_is_disabled":false,"inline_featured_image":false,"c2c_always_allow_admin_comments":false,"footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":[]},"categories":[4],"tags":[1148,1115],"jetpack_publicize_connections":[],"acf":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/css-tricks.com\/wp-content\/uploads\/2017\/02\/csd.jpeg?fit=1280%2C853&ssl=1","jetpack-related-posts":[],"featured_media_src_url":"https:\/\/i0.wp.com\/css-tricks.com\/wp-content\/uploads\/2017\/02\/csd.jpeg?fit=1024%2C682&ssl=1","_links":{"self":[{"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/posts\/251754"}],"collection":[{"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/users\/247919"}],"replies":[{"embeddable":true,"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/comments?post=251754"}],"version-history":[{"count":23,"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/posts\/251754\/revisions"}],"predecessor-version":[{"id":252091,"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/posts\/251754\/revisions\/252091"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/media\/251767"}],"wp:attachment":[{"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/media?parent=251754"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/categories?post=251754"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/css-tricks.com\/wp-json\/wp\/v2\/tags?post=251754"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}