
Select the tightest bigOh notation for the following expressions:
i) 4 + 8 + 12 + 16 + ..... + 4n
ii) 1 + 2 + 4 + 8 + 16 + ..... + n
iii) n*(1 + 2 + 3 + ..... + n)
iv) log (n^2) + (log n)^2
v) n + 2^(2*log(n))

Show the following:
i) n! = O(n^n)
ii) 1^2 + 2^2 + 3^2 + ..... + n^2 = Theta (n^3)
iii) n / (sqrt(n) + 1) = O(n)
iv) sqrt(n) + log(n) = Omega(sqrt(n))

Using mathematical induction, show that:
1^2 + 2^2 + 3^2 + ..... + n^2 = n(n+1)(2n+1)/6

Analyze the complexity (in bigOh terms) of the following selectionsort
routine. The routine picks out the largest element in the current list
and exchanges it with the last element. It continues until the list has
only one element:
for (i = n1; i > 0; i) {
MaxPosition = i;
for (j = 0; j < i; j++) {
if (a[j] > a[MaxPosition])
MaxPosition = j;
}
exchange(i, MaxPosition);
}

a) Give a Theta(n) algorithm for computing a^n, given a and n.
b) Give a Theta(log n) algorithm for computing a^n, given that n is a
power of 2.

You are given a data structure stack with the following ADT:
push(element)
pop()
size()
Each of these operations runs in O(1) time. Use pseudocode to implement
the following Queue ADT using the stack ADT only. What is the complexity
of each of your methods?
enqueue(element)
dequeue()
size()
Note: you do not have to implement a linked list or an array. Instead,
you must use only the three methods in the stack ADT.
Hint: Use multiple stacks.

Insertion into Ranked Sequences implemented as arrays take O(n) time
and location in positional sequences using linked lists taks O(n) time.
Describe an implementation using a linked list of fixed size arrays that
reduces this time. Assume that each node in the linked list contains a
count of the number of elements in array of the node. If an element
must be inserted between two nodes whose arrays are filled, a new
node is created in between and the element is inserted into the node.
Note that there may be partially filled arrays in the list. If the
array in each linked list node is capable of carrying 10 elements, what
is the runtime of this data structure for location and insertion (do
not ignore any constants). Write pseudocode for location and insertion.
(While computing complexities, assume that all nodes in the linked list
are full.)