Every problem can have multiple solutions

• Problem: Sorting
• Possible Solutions:
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Etc.

When thinking about the various solutions on the table, we need to be able to pick the best one.

Simply choosing 1 or 2 data sets and running them against the implemented algorithms doesn’t really prove anything

• Dependent on computer that you’re running on
• Dependent on the quality of implementation in whatever language you choose (in other words, how good is your translation from algorithm to actual code?)
• What happens if the data sets get bigger and bigger?

When thinking about which algorithm is better, we can look at that from various perspectives. Different metrics we could use include:

• Time to execute
• Amount of memory needed to execute
• Readability/maintainability of solution
• Network throughput
• Etc.

We will focus on Time Efficiency.

We use the Random Access Machine (RAM) Model of computation to analyze algorithms separate from implementing them in a particular programming language.

• RAM computer has infinite memory and every operation takes the same amount of time to execute.
• To evaluate the performance of an algorithm, we attempt to develop a function that represents the number of primitive operations needed to complete the algorithm in for a given input of size n. We usually call the function T(n).
• T(n) represents the number of primitive ops for an algorithm to complete.
• Primitive operations include:
  • Basic arithmetic operations: +, -, *, /
  • Basic comparison operations: <, >, ==, ≤, ≥
  • Variable access

Back to Problem P with 2 or more viable solutions A and B:

• We can develop a T(n) for A and a T(n) for B.

• For example:

  $$ T_A(n)=2n^2+3n+4

  $$

  $$ T_B(n)=4n+10 $$

Big O

• Let f and g be real-valued functions. We say that f(n) is O(g(n)) if there exists n_0 > 0 and c > 0 such that for all n ≥ n_0, f(n) ≤ c*g(n).

Big O analysis allows us to disregard coefficients and lower order terms of our T(n) functions.

• Example, we never say O(2n) or O(n^2 + 3n).

We end up with a list of categories that most algorithms fall into:

• O(1) - Constant
• O(lg n) - Logarithmic
• O(n) - Linear
• O(n lg n) - Log Linear
• O(n^2) - Quadratic
• O(n^3) - Cubic
• O(2^n) - Exponential

Some Examples

• In these examples, n represents the size of an input data set.

//This example is O(n)

int s = 0;
for (int i = 0; i < n; i++)
	s++;

//This example is O(n^2)

int s = 0;
for (int i = 0; i < n; i++)
	for(int j = 0; j < n; j++)
		s++;

//This example is O(lg n)

int s = 0; 
for (int i = 1; i < n; i *= 2)
	s++;

//This example is O(n lg n)

int s = 0;
for (int i = 0; i < n; i++)
	for(int j = n; j >= 1; j /= 2)
		s++;