We can express the runtime of a function in terms of it’s operations, its compares, its iterations, or many other ways
The runtime usually involves a summation with the cost of the operation and the frequency of the operation
`

for (i = 1, i <= n, i += 1)
    <do something>
endfor

The number of iterations is $T (n) = \sum_{i = 1}^{n} 1 = n$
The number of compares is $T (n) = i = 1 \sum n + 1 1 = n + 1$
Basically we have to analyze the for loop, pick out what the bounds of our summation will be, and use that to create a runtime expression. Then solve the runtime expression.

Useful Tips

When the variable is increasing by 1, we can write the summation in terms of that variable. However, when it is not increasing by one, we need to rewrite the loop so that it is.
Here the loop has i increasing by 2. So, we write down all the numbers i is up to n. Then we figure out what k can be so that k only increases by one each time. In this case, if we say $2 * k + 1$ we end up with an expression where k is constantly increasing. We can then replace everywhere we see i in the loop with k and solve them to find our new bounds. We set 2k+1 = n and solve for k to find the upper bound, and the lower bound was i = 1, so now its 2k+1 = 1, solve for k.
When the for loop is $< n$ we say the upper bound of the summation is $n - 1$ . If the for loop is $\leq n$ then the upper bound is just $n$
If we have a loop with a multiplication or division, then we are almost certainly going to need Log Rules.
Multiple for loops are summations of summations

Log Rules

In CS251, a log is almost always going to be base 2 unless explicitly said otherwise
$lo g (ab) = lo g (a) + lo g (b)$
$lo g (\frac{a}{b}) = lo g (a) - lo g (b)$
Given 2 numbers $a$ and $b$ , $lo g_{a} (n) = \frac{l o g _{b} ( n )}{l o g _{b} ( a )}$
$lo g (n^{a}) = a lo g (n)$
$a^{l o g_{a} (n)} = n$
$a^{c l o g_{a} (n)} = n^{c}$

Given $c$ is a constant, $\sum_{i = m}^{n} c = c (n - m + 1)$
$\sum_{i = 1}^{n} i = \frac{1}{2} n (n + 1)$
$\sum_{i = 1}^{n} i^{2} = \frac{1}{6} n (n + 1) (2 n + 1)$
Given a function $f (i)$ , $\sum_{i = m}^{n} f (i) = \sum_{i = 1}^{n} f (i) - \sum_{i = 1}^{m - 1} f (i)$