Big-O Analysis

Problem 1

Problems 
1        5
2        6
3
4


Answers
1. O(n)
2. O(n^2)
3. O(n^3)
4. O(log_2(n))

// k goes from n to n/2 to n/4... 
// It takes log_2(n) steps to finish.

5. O(n*log_3(n))
6. O(n^3)

Problem 2

void mystery(int n)
{
	for (int q=0; q<n; q++)
    {
    	for (int x=0; x<q; x++)
        {
        	cout << "Waahoo!!";
        }
    }
}

cout statement will run a total of 
0 + 1 + ... + n-1 times, which is n(n-1)/2

Big-O: O(n^2)

Problem 3

Problems
1       3 
2       4

Answers
1. O(n^2*q)
2. O(n+q^2)
3. O(n^2)
4. O(n+q)

STL and Big-O

Algorithms that STL classes have Big-Os too.

find(): O(log_2(n))

Answer: O(D*log_2(n))

Example

1. Access an item: O(1)
2. Erase the first item: O(q)
3. Push back: O(1)
4. Result: O(q*(1+q+1)) = O(q^2)

STL and Big-O Cheat Sheet

Problem 4

Answer: O(p^2)

---

There are q^2 total iterations (items), and the cost of adding a single item to a set with q^2 items is O(log_2(q^2)).

Answer: O(q^2*log_2(q^2))

---

Answer: O(z)

Problem 5

Q. What is the Big-O of determining if the first set, v[0], 
contains the value 7?
A. O(log_2(Q))

Q. What is the Big-O of determining if any set in v has 
a value of 7?
A. O(N*log_2(Q))

Q. What is the Big-O of determining the number of even values in 
all of v?
A. O(N*Q*log_2(Q))

Q. What is the Big-O of finding the first set with a value of 7 
and then counting the number of even values in that set?
A. O(N*(log_2(Q)) + Q*log_2(Q))

Sort

Selection Sort

void selectionSort(int A[], int n)
{
    for (int i=0; i<n; i++) {
        int midIndex = i;
        for (int j=i+1; j<n; j++) {
          	if (A[j] < A[minIndex]) 
            	    minIndex = j;
          }
          swap(A[i], A[midIndex]);
    }
}

Selection sort is unstable.
used for easy algorithms, small data sets.

Insertion sort

// ascending order
void insertionSort(int A[], int n)
{
    for(int s=2; s<=n; s++) {
    	int sortMe = A[s-1];
        int i = s-2;
        while(i>=0 && sortMe < A[i]) {
        	A[i+1] = A[i];
            --i;
        }
        
        A[i+1] = sortMe;
    }
}

Bubble Sort

void bubbleSort(int Arr[], int n)
{
   bool atLeastOneSwap;
   do 
   {
        atLeastOneSwap = false;
        for (int j=0; j<(n-1); j++) {
            if (Arr[j] > Arr[j+1]) {
                Swap(Arr[j], Arr[j+1]);
                atLeastOneSwap = true;
            }
        }
    }
    while (atLeastOneSwap == true);
}