Exponent

$$X, X^2, = X X, X^3= XX*X$$

// O(N) Time Complexity
for(int i=0; i< N, i++){
	A[i] = 0;
}

$X^A = B$ if and only $log_x B= A$

Theorom 1.1

$$log_aB = (log_cB)/ (log_cA)$$

$log(x)$ refers to base 2 in our case. For Binary

---

Not Included in the Exam Review PDF Study For Exam - Just [[Notes_5]]

Induction Example

$F_i < (\frac{5}{3})^i , for ..i ≥ 1$

Base Case: When $i = 1, F_1 = 1 < (\frac{5}{3})^1$ Induction Hypothesis: $(\frac{5}{3})^i, for i ≥ 1 ..and.. i ≤ k$ We need to prove that the induction case when $i=k+1$