How to do an analysis in 5 steps

Doing mathematical analysis can be intimidating. However, what you are really doing is simply explaining a thought process. This can be done in a fairly consistent step by step manner. This section looks at the steps you should take to do this and break down how to approach an analysis.

Step 0: It is good to start by putting your code in.

info

If you are writing out an analysis for a lab or assignment, it is a good idea to start by providing the snippet of the code you are analyzing so that you have a reference.

Python

def factorial (n):
    rc = 1

    # multiplying 1*x gives x, so we can skip it
    for i in range(2, n + 1):
        rc = rc * i
    return rc

C++

unsigned int factorial (unsigned int n){
    unsigned int rc = 1;

    // multiplying 1*x gives x, so we can skip it
    for (unsigned int i=2;i<=n;i++){
        rc=rc*i;
    }
    return rc;
}

tip

If you are copying code into a markdown page, you can use surround the code block with ``` to do a block quote.

To format according to a language provide the name of the language after the third tick that precedes the block. For example:

``` cpp

put your code here. code will be c++ syntax formatted

```

``` python

put your code here. code will be python syntax formatted

```

Step 1: Establish variables and functions (mathematical ones):

info

Similar to writing a program you want to declare your variables and function prototypes first. You need to do this to establish context... variables need a meaning, functions need a meaning. You need to state what they represent first. These statements need to be placed above the code block

Let $n$ represent the value we are finding the factorial for

Let $T(n)$ represent number of operations needed to find n! using the code below:

Step 2: Count your operations

info

In this step you are explaining how it is that you come up with your final equation. Essentially, you are establishing the logic behind the mathematical statement you will make in step 3

Put the operation count in a comment beside each line of the code blurb. The loop runs n-1 times (i goes from 2 to n inclusive). Thus any operations that occur in the loop is counted as n-1.

Python

def factorial (number):
    rc = 1                                  # 1

    for i in range(2,n+1):                  # (n-1) + 1 + 1
                                                # (n-1) loop iterations
                                                # 1 more for + operator
                                                # 1 more for call to range function
        rc = rc * i                         # 2 (n-1)
                                                # 2 as there are two operators
                                                # (n-1) as loop runs n-1 times
    return rc                               # 1

Step 3: Establish the Mathematical Expression for T(n)

info

Based on the counts from step 2, put together an expression for T(n) you can even express the condition for when the expression is true... for example

We add up the operation counts in the comments

$T(n) = 1 + (n-1) + 1 + 1 + 2(n-1) + 1$

Step 4: Simplify your Equation

info

When you first write out your expression in step 3, the formula isn't always a polynomial. You should start by simplifying your equation. You want to establish a mathematical equation of the form:

$T(n) = a_xn^x+a_{x-1}n^{n-1}+ a_{x-2}n^{n-2}...+a_1x+1$

$\begin{aligned} T(n) &= 1 + (n-1) + 1 + 1 + 2(n-1) + 1 \\ &= 3(n-1) +4 \\ &= 3n-3 +4 \\ &= 3n +1 \end{aligned}$

Step 5: State your final result.

Therefore, $T(n)$ is $O(n)$

info

Once you have a polynomial, you can find the dominating term. This is the term that, as n becomes bigger and bigger, the other terms become so insignificant that they no longer matter. In this case the term is $3n$. Remove the constant 3. We don't need it because the definition of big-O allows us to stretch the curve. Putting it in will make it look like you don't understand the definition so typically you remove it.

C++

unsigned int factorial (unsigned int n){
    unsigned int rc = 1;                    // 1
    for (unsigned int i=2;i<=n;i++){        // 1 + (n-1) + (n-1)
                                                // 1 for i = 2
                                                // (n-1)'s for i<=n and i++ as
                                                // these run for each iteration
                                                // of loop and loop runs n-1
                                                // times
            rc = rc * i;                    // 2 (n-1)
                                                //2 because two operators
                                                //(n-1) as loop runs n-1 times
    }
    return rc;                              // 1
}

Step 3: Establish the Mathematical Expression for T(n)

info

Based on the counts from step 2, put together an expression for T(n) you can even express the condition for when the expression is true... for example

We add up the operation counts in the comments

$T(n) = 1 + 1 + (n-1) + (n-1) + 2(n-1) + 1$

Step 4: Simplify your Equation

info

When you first write out your expression in step 3, the formula isn't always a polynomial. You should start by simplifying your equation. You want to establish a mathematical equation of the form:

$T(n) = a_xn^x+a_{x-1}n^{n-1}+ a_{x-2}n^{n-2}...+a_1x+1$

$\begin{aligned} T(n) &=1 + 1 + (n-1) + (n-1) + 2(n-1) + 1 \\ &= 4(n-1) +3 \\ &= 4n-4 +3 \\ &=4n -1 \end{aligned}$

Step 5: State your final result.

Therefore, $T(n)$ is $O(n)$

info

Once you have a polynomial, you can find the dominating term. This is the term that, as n becomes bigger and bigger, the other terms become so insignificant that they no longer matter. In this case the term is $4n$. Remove the constant 4. We don't need it because the definition of big-O allows us to stretch the curve. Putting it in will make it look like you don't understand the definition so typically you remove it.