BigONotation.ptx

<?xml version="1.0" ?><section xml:id="algorithm-analysis_big-o-notation">
    <title>Big-O Notation</title>
    <p>When trying to characterize an algorithm's efficiency in terms of
        execution time, independent of any particular program or computer, it is
        important to quantify the number of operations or steps that the
        algorithm will require. If each of these steps is considered to be a
        basic unit of computation, then the execution time for an algorithm can
        be expressed as the number of steps required to solve the problem.
        Deciding on an appropriate basic unit of computation can be a
        complicated problem and will depend on how the algorithm is implemented.</p>
    <p>A good basic unit of computation for comparing the summation algorithms
        shown earlier might be to count the number of assignment statements
        performed to compute the sum. In the function <c>sumOfN</c>, the number of
        assignment statements is 1 (<m>theSum = 0</m>)
        plus the value of <em>n</em> (the number of times we perform
        <m>theSum=theSum+i</m>). We can denote this by a function, call it T,
        where <m>T(n)=1 + n</m>. The parameter <em>n</em> is often referred to as
        the <q>size of the problem,</q> and we can read this as <q>T(n) is the time
        it takes to solve a problem of size n, namely 1+n steps.</q></p>
    <p>In the summation functions given above, it makes sense to use the number
        of terms in the summation to denote the size of the problem. We can then
        say that the sum of the first 100,000 integers is a bigger instance of
        the summation problem than the sum of the first 1,000. Because of this,
        it might seem reasonable that the time required to solve the larger case
        would be greater than for the smaller case. Our goal then is to show how
        the algorithm's execution time changes with respect to the size of the
        problem.</p>
    <p>Computer scientists prefer to take this analysis technique one step
        further. It turns out that the exact number of operations is not as
        important as determining the most dominant part of the <m>T(n)</m>
        function. In other words, as the problem gets larger, some portion of
        the <m>T(n)</m> function tends to overpower the rest. This dominant
        term is what, in the end, is used for comparison.<idx>order of magnitude</idx> The <term>order of
            magnitude</term> function describes the part of <m>T(n)</m> that increases
        the fastest as the value of <em>n</em> increases.<idx>big-O notation</idx> Order of magnitude is often
        called <term>Big-O notation</term> (for <q>order</q>) and written as
        <m>O(f(n))</m>. It provides a useful approximation to the actual
        number of steps in the computation. The function <m>f(n)</m> provides
        a simple representation of the dominant part of the original
        <m>T(n)</m>.</p>
    <p>In the above example, <m>T(n)=1+n</m>. As <em>n</em> gets large, the
        constant 1 will become less and less significant to the final result. If
        we are looking for an approximation for <m>T(n)</m>, then we can drop
        the 1 and simply say that the running time is <m>O(n)</m>. It is
        important to note that the 1 is certainly significant for
        <m>T(n)</m>. However, as <em>n</em> gets large, our approximation will be
        just as accurate without it.</p>
    <p>As another example, suppose that for some algorithm, the exact number of
        steps is <m>T(n)=5n^{2}+27n+1005</m>. When <em>n</em> is small, say 1 or 2,
        the constant 1005 seems to be the dominant part of the function.
        However, as <em>n</em> gets larger, the <m>n^{2}</m> term becomes the most
        important. In fact, when <em>n</em> is really large, the other two terms become
        insignificant in the role that they play in determining the final
        result. Again, to approximate <m>T(n)</m> as <em>n</em> gets large, we can
        ignore the other terms and focus on <m>5n^{2}</m>. In addition, the
        coefficient <m>5</m> becomes insignificant as <em>n</em> gets large. We
        would say then that the function <m>T(n)</m> has an order of
        magnitude <m>f(n)=n^{2}</m>, or simply that it is <m>O(n^{2})</m>.</p>


    <p>Although we do not see this in the summation example, sometimes the
        performance of an algorithm depends on the exact values of the data
        rather than simply the size of the problem. For these kinds of
        algorithms we need to characterize their performance in terms of <idx>best case</idx><term>best 
        case</term>, <idx>worst case</idx><term>worst case</term>, or <idx>average case</idx><term>average case</term> performance. The worst-case
        performance refers to a particular data set where the algorithm performs
        extremely poorly. At the same time, a different data set for the exact
        same algorithm might have outstanding performance. However, in most
        cases the algorithm performs somewhere in between these two extremes
        (average case). It is important for a computer scientist to understand
        these distinctions so they are not misled by one particular case.</p>
    <p>A number of very common order of magnitude functions will come up over
        and over as you study algorithms. These are shown in <xref ref="algorithm-analysis_algorithm-analysis_tbl-fntablecpp"/>. In
        order to decide which of these functions is the dominant part of any
        <m>T(n)</m> function, we must see how they compare with one another
        as <em>n</em> gets large.</p>
    
    <table xml:id="algorithm-analysis_algorithm-analysis_tbl-fntablecpp">
        <title>Common Big-O Functions</title>
        <tabular>
        
            
            
            
                <row header="yes">
                    <cell>
                        <term>f(n)</term>
                    </cell>
                    <cell>
                        <term>Name</term>
                    </cell>
                </row>
            
            
                <row>
                    <cell>
                        <m>1</m>
                    </cell>
                    <cell>
                        Constant
                    </cell>
                </row>
                <row>
                    <cell>
                        <m>\log n</m>
                    </cell>
                    <cell>
                        Logarithmic
                    </cell>
                </row>
                <row>
                    <cell>
                        <m>n</m>
                    </cell>
                    <cell>
                        Linear
                    </cell>
                </row>
                <row>
                    <cell>
                        <m>n\log n</m>
                    </cell>
                    <cell>
                        Log Linear
                    </cell>
                </row>
                <row>
                    <cell>
                        <m>n^{2}</m>
                    </cell>
                    <cell>
                        Quadratic
                    </cell>
                </row>
                <row>
                    <cell>
                        <m>n^{3}</m>
                    </cell>
                    <cell>
                        Cubic
                    </cell>
                </row>
                <row>
                    <cell>
                        <m>2^{n}</m>
                    </cell>
                    <cell>
                        Exponential
                    </cell>
                </row>
            
        
    </tabular></table>
    <p><xref ref="fig-graphfigurecpp"/> shows graphs of the common
        functions from <xref ref="algorithm-analysis_algorithm-analysis_tbl-fntablecpp"/>. Notice that when <em>n</em> is small, the
        functions are not very well defined with respect to one another. It is
        hard to tell which is dominant. However, as <em>n</em> grows, there is a
        definite relationship and it is easy to see how they compare with one
        another.</p>
    
    <figure xml:id="fig-graphfigurecpp">
        <caption>Common Big-O Functions</caption>
            <image source="AlgorithmAnalysis/newplot.png" width="50%">
                <description><p>This figure shows graphs of the common functions from <xref ref="algorithm-analysis_algorithm-analysis_tbl-fntablecpp"/>.
                    When n is small, the functions are not very well defined with respect to one another. It is hard to tell which is
                    dominant. However, as n grows, there is a definite relationship and it is easy to see how they compare with one another.
                </p></description>
            </image>
    </figure>

        <p>As a final example, suppose that we have the fragment of C++ code
        shown in <xref ref="algo_analysis_dummycode_1"/>. Although this program does not really do
        anything, it is instructive to see how we can take actual code and
        analyze performance.</p>
    
    <exploration xml:id="expl-dummycode_1">
        <title>Analysis Example</title>
        <task label="algo_analysis_dummycode_1" xml:id="algo_analysis_dummycode_1">
            <title>C++ Implementation</title>
            <statement><program language="cpp" label="algo_analysis_dummycode_1-prog"><code>
#include &lt;iostream&gt;
using namespace std;

int main(){
    int a=5;
    int b=6;
    int c=10;
    for (int i=0; i&lt;n; i++){
        for (int j=0; j&lt;n; j++){
            int x = i * i;
            int y = j * j;
            int z = i * j;
        }
    }

    for (int k = 0; k &lt; n; k++){
        int w = a*k + 45;
        int v = b*b;
    }
    int d = 33;
    return 0;
}
            </code></program></statement>
        </task>
        <task xml:id="algo_analysis_dummycode_1_py" label="algo_analysis_dummycode_1_py">
            <title>Python Implementation</title>
            <statement><program language="python" label="algo_analysis_dummycode_1_py-prog"><code>
def main():
    a=5
    b=6
    c=10
    for i in range(n):
        for j in range(n):
            x = i * i
            y = j * j
            z = i * j
    for k in range(n):
        w = a*k + 45
        v = b*b
    d = 33
main()
            </code></program></statement>
        </task>
    </exploration>
    <p>The number of assignment operations is the sum of four terms. The first
        term is the constant 3, representing the three assignment statements at
        the start of the fragment. The second term is <m>3n^{2}</m>, since
        there are three statements that are performed <m>n^{2}</m> times due
        to the nested iteration. The third term is <m>2n</m>, two statements
        iterated <em>n</em> times. Finally, the fourth term is the constant 1,
        representing the final assignment statement. This gives us
        <m>T(n)=3+3n^{2}+2n+1=3n^{2}+2n+4</m>. By looking at the exponents,
        we can easily see that the <m>n^{2}</m> term will be dominant and
        therefore this fragment of code is <m>O(n^{2})</m>. Note that all of
        the other terms as well as the coefficient on the dominant term can be
        ignored as <em>n</em> grows larger.</p>
    
    <figure xml:id="fig_graphfigure2cpp">
        <caption>Comparing <m>T(n)</m> with Big-O Functions</caption>
            <image source="AlgorithmAnalysis/newplot2.png" width="50%">
                <description><p>This figure shows a few of the common Big-O functions as they compare with the T(n) function discussed above. Note that T(n) is initially larger than the cubic function. However, as n grows, the cubic function quickly overtakes T(n). It is easy to see that T(n) then follows the quadratic function as n continues to grow.</p></description>
            </image>
    </figure>

    <p><xref ref="fig_graphfigure2cpp"/> shows a few of the common Big-O functions as they
        compare with the <m>T(n)</m> function discussed above. Note that
        <m>T(n)</m> is initially larger than the cubic function. However, as
        n grows, the cubic function quickly overtakes <m>T(n)</m>. It is easy
        to see that <m>T(n)</m> then follows the quadratic function as
        <m>n</m> continues to grow.</p>

<reading-questions xml:id="rq-big-o-notation">
    <title>
Reading Questions
    </title>
    <exercise label="bigo3">
        <statement>
    
        <p>If the exact number of steps is <m>T(n)=2n+3n^{2}-1</m> what is the Big O?</p>
    
        </statement>
    <choices>
    
            <choice>
                <statement>
                    <p>O(<m>2n</m>)</p>
                </statement>
                <feedback>
                    <p>No, <m>3n^{2}</m> dominates 2n. Try again.</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>O(<m>n</m>)</p>
                </statement>
                <feedback>
                    <p>No, <m>n^{2}</m> dominates n. Try again.</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>O(<m>3n^{2}</m>)</p>
                </statement>
                <feedback>
                    <p>No, the 3 should be omitted because <m>n^{2}</m> dominates.</p>
                </feedback>
            </choice>
    
            <choice correct="yes">
                <statement>
                    <p>O(<m>n^{2}</m>)</p>
                </statement>
                <feedback>
                    <p>Right!</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>More than one of the above</p>
                </statement>
                <feedback>
                    <p>No, only one of them is correct. Try again.</p>
                </feedback>
            </choice>
    </choices>
    
    </exercise>

    <exercise label="parsonsBigO" language="python"><statement>
        <p>Without looking at the graph above, from top to bottom order the following from most to least efficient.</p>
    </statement>
    <blocks><block order="1">
    <cline>constant</cline>
    <cline>logarithmic</cline>
    <cline>linear</cline>
    <cline>log linear</cline>
    <cline>quadratic</cline>
    <cline>cubic</cline>
    <cline>exponential</cline>
    </block></blocks></exercise>

    <exercise label="crossoverefficiency">
        <statement>
    
        <p>Which of the following statements is true about the two algorithms?
            Algorithm 1: 100n + 1
            Algorithm 2: n^2 + n + 1</p>
    
        </statement>
    <choices>
    
            <choice>
                <statement>
                    <p>Algorithm 1 will require a greater number of steps to complete than Algorithm 2</p>
                </statement>
                <feedback>
                    <p>This could be true depending on the input, but consider the broader picture</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>Algorithm 2 will require a greater number of steps to complete than Algorithm 1</p>
                </statement>
                <feedback>
                    <p>This could be true depending on the input, but consider the broader picture</p>
                </feedback>
            </choice>
    
            <choice correct="yes">
                <statement>
                    <p>Algorithm 1 will require a greater number of steps to complete than Algorithm 2 until they reach the crossover point</p>
                </statement>
                <feedback>
                    <p>Correct!</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>Algorithm 1 and 2 will always require the same number of steps to complete</p>
                </statement>
                <feedback>
                    <p>No, the efficiency of both will depend on the input</p>
                </feedback>
            </choice>
    </choices>
    
    </exercise>
    

    <exercise label="BIGO1">
        <statement>
    
            <p>The Big O of a particular algorithm is <m>O(\log_{2}n)</m>.
                Given that it takes 2 seconds to complete the algorithm with 3 million inputs;
                how long would it take with 4 million inputs?</p>
    
        </statement>
    <choices>
    
            <choice>
                <statement>
                    <p>3.444</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again.</p>
                </feedback>
            </choice>
    
            <choice correct="yes">
                <statement>
                    <p>2.04</p>
                </statement>
                <feedback>
                    <p>Correct!</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>4</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again.</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>More than one of the above</p>
                </statement>
                <feedback>
                    <p>No, only one of them is correct. Try again.</p>
                </feedback>
            </choice>
    </choices>
    
    </exercise>
    <exercise label="BIGO2">
        <statement>
    
            <p>The Big O of a particular algorithm is <m>O(\log_{2}n)</m>.
                Given that it takes 2 seconds to complete the algorithm with 3 million inputs;
                how long would it take with <em>10 million</em> inputs?</p>
    
        </statement>
    <choices>
    
            <choice>
                <statement>
                    <p>3.444</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again.</p>
                </feedback>
            </choice>
    
            <choice correct="yes">
                <statement>
                    <p>2.16</p>
                </statement>
                <feedback>
                    <p>Correct!</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>2</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again.</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>4.2</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>More than one of the above</p>
                </statement>
                <feedback>
                    <p>No, only one of them is correct. Try again.</p>
                </feedback>
            </choice>
    </choices>
    
    </exercise>
    <exercise label="BIGO3">
        <statement>
    
            <p>The Big O of a particular algorithm is <m>O(n^{3})</m>.
                Given that it takes 2 seconds to complete the algorithm with 1000 inputs;
                how long would it take with 2000 inputs?</p>
    
        </statement>
    <choices>
    
            <choice>
                <statement>
                    <p>2000</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again. Think about what happens to the time as more operations occur.</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>3000</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again. Think about what happens to the time as more operations occur.</p>
                </feedback>
            </choice>
    
            <choice correct="yes">
                <statement>
                    <p>16</p>
                </statement>
                <feedback>
                    <p>Correct!</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>1500</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again. Think about what happens to the time as more operations occur.</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>More than one of the above</p>
                </statement>
                <feedback>
                    <p>No, only one of them is correct. Try again.</p>
                </feedback>
            </choice>
    </choices>
    
    </exercise>

    <exercise label="BIGO4">
        <statement>
    
            <p>The Big O of a particular algorithm is <m>O(n^{3})</m>.
                Given that it takes 2 seconds to complete the algorithm with 1000 inputs;
                how long would it take with 10,000 inputs?</p>
    
        </statement>
    <choices>
    
            <choice correct="yes">
                <statement>
                    <p>2000</p>
                </statement>
                <feedback>
                    <p>Right!</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>3000</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again. Think about what happens to the time as more operations occur.</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>16</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again. Think about what happens to the time as more operations occur.</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>1500</p>
                </statement>
                <feedback>
                    <p>Incorrect. Try again. Think about what happens to the time as more operations occur.</p>
                </feedback>
            </choice>
    
            <choice>
                <statement>
                    <p>More than one of the above</p>
                </statement>
                <feedback>
                    <p>No, only one of them is correct. Try again.</p>
                </feedback>
            </choice>
    </choices>
    
    </exercise>
</reading-questions>
<p>
    <!-- extra space before the progress bar -->
</p>
</section>