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.

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.

unsigned int factorial (unsigned int n){
    unsigned int rc = 1;
    //multiplying 1*1 gives 1 so we don't start from 1
    for (unsigned int i=2;i<=n;i++){
        rc=rc*i;
    }
    return rc;
}

If you are copying code into a markdown wiki 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

```

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

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

Step 2: Count your operations

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.

unsigned int factorial (unsigned int n){
    unsigned int rc = 1;                    // 1
    //multiplying 1*1 gives 1 so we don't start from 1
    for (unsigned int i=2;i<=n;i++){        //1 + (n-1) + (n-1)
        rc=rc*i;                            //2(n-1)
    }
    return rc;                              //1
}

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

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

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{align*} T(n) &=1 + 1 + (n-1) + (n-1) + 2(n-1) + 1 \\ &= 4(n-1) +3 \\ &= 4n-4 +3 \\ &=4n -1 \end{align*}

Step 5: State your final result.

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.

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