## Quiz #3 Prep

First, we will briefly go over the following topics:

1. Efficiency and Asymptotics: Big-O, Big-Omega, Big-Theta
2. Recursion, Searching
6. General Trees and Binary Trees: Structures and Traversals (pre-order, in-order, post-order)


## Efficiency and Asymptotics

Prove the following:
1. $8n^2+15$ is $O(n^2)$ and $O(n^3)$
2. $15n^4+n^2-n-10$ is $O(n^4)$
3. $5n^2+4n$ is $\Omega(n)$ and $\Theta(n^2)$

In terms of big-O notation and $n$, give the running time of the following code snippets:

for (int i = 0; i < 4; i++) {
for (int j = 1; j < n; j++) {
for (int k = j; k < n; k++) {
doStuff();
}
}
}


## Recursion, Searching

What is wrong with the following piece of code? Fix it.

public static int multiplier(n, m) {
return n + multiplier(n, m-1);
}


Write a method to return the sum of all the integers in a list using recursion.
Given a random list of integers, what is the most efficient to search for some number? Why?

Suppose you have a Node class that looks like:

private Node<T> {
public T val;
public Node<T> next;
public Node(T value) {
val = value;
}
}


Write a method to create a circularly singly linked structure that looks like:

A -> B -> C -> D -> E ---------
/\                            |
|                             |
|------------------------------


Next, remove E, then B so that you have:

A -> C -> D -------------------
/\                            |
|                             |
|------------------------------


Next, insert G between A and C to get:

A -> G -> C -> D --------------
/\                            |
|                             |
|------------------------------


## Trees

Produce the pre-order, in-order, and post-order traversal results of the tree below:

           A
/ \
E  B
/   / \
H    C  D
\  \
I  F
\
G