Algorithm Analysis

An algorithm is a step-by-step description of how to solve a “problem”

There are three types of efficiency:

• Time efficiency
• Space efficiency
• Power efficiency

<aside> 💡 Big O Notation (more formal definition) $O(g(n))$ is the set of all functions whose order is less than or equal to $g(n)$

</aside>

Example 1:

for (i = 1; i <= n; ++i) {
  printf("*");
}

Example 2:

sum = 0;
for (i = 0; i < n; ++i) {
  sum += i; 
}

$$ ans = \sum_{i=1}^n{O(1)} = O(n) $$

Example 3:

k = n;              // n is size of the data 
while (k > 0) {
  printf("*");
  k -= 10; 
}

$$ ans = \sum_{i=1}^{n/10}O(1) = O(n) $$

Example 4:

k = n;              // n is size of the data 
while (k > 0) {
  printf("*");
  k /= 10; 
}