Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    3

    Uploaded by

    s39769748

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    3

    Uploaded by

    s39769748
    2 views1 page

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    2 views1 page

    3

    Uploaded by

    s39769748

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 1

    52 2 Computational Complexity

    copy operations. The third append requires three copy operations. So, we have the
    following number of list elements being copied.
    
    n
    1 + 2 + 3 + 4 + ··· + n = i
    i=1
    
    In mathematics we can express this sum with a summation symbol (i.e. ). This is
    the mathematical way of expressing the sum of the first n integers. But, what is this
    equal to? It turns out with a little work, we can find that the following is true.
    
    n
    n(n + 1)
    i=
    2
    i=1
    We can prove this is true using a proof technique from Mathematics called mathe-
    matical induction. There are a couple of variations of mathematical induction. We’ll
    use what is called weak induction to prove this. When proving something using
    induction you are really constructing a meta-proof. A meta-proof is a set of steps
    that you can repeat over and over again to find your desired result. The power of
    induction is that once we have constructed the meta-proof, we have proved that the
    result is true for all possible values of n.
    We want to prove that the formula given above is valid for all n. To do this we
    first show it is true for a simple value of n. In our case we’ll pick 1 as our value of
    n. In that case we have the following.
    
    1
    1(1 + 1)
    i =1=
    2
    i=1
    This is surely true. This step is called the base case of the inductive proof. Every
    proof by induction must have a base case and it is usually trivial.
    The next step is to create the meta-proof. This meta-proof is called the inductive
    case. When forming the inductive case we get to assume that the formula holds for all
    values, m, where m is less than n. This is called strong induction. In weak induction we
    get to assume that the formula is valid for n −1 and we want to show that it is valid for
    n. We’ll use weak induction in this problem to finish our proof. Again, this step helps
    us form a set of steps that we can apply over and over again to get from our base case
    to whatever value of n we need to find. To begin we will make note of the following.
     n n−1 
    i= i +n
    i=1 i=1
    This is true by the definition of summation. But now we have a sum that goes to n − 1
    and weak induction says that we know the equation is valid for n − 1 . This is called
    the inductive hypothesis. Since it holds for n − 1 we know the following is true.
    We get this by substituting n − 1 everyplace that we see an n in the original formula.
    
    n−1
    (n − 1)n
    i=
    2
    i=1

    This copy belongs to 'acha04'

    You might also like