CS 14 - Homework 1

Due Tuesday, April 16 (at beginning of class)

1. Write the Big-Oh notation for the following functions:

1. 4n² + 2n + 5

2. 2n(3n² + 5n (6n + 4))

2. Given the following running times, rank them from fastest to slowest (for large n).

nlogn, 4n²+n+8, 10logn, 2n+nlogn, 46n², 7n-11.

3. For each of the following program fragments, write a mathematical function to describe the running time of the code and give the corresponding Big-Oh notation.

1. x=0

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

x++

2. x=0

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

for(j=0; j<i; j++)

x++

4. Program A has a running time of n²-1500, where n is the size of the input. Program B has running time 400n+16. For what values of n does program A run faster? For what values of n does program B run faster?

5. Draw a singly linked list that contains three items X, Y, and Z. The head pointer points to the X item. Now explicitly write out the pointer operations required for each of the following parts (each part operates on the original list).

1. insert D at end
2. insert D before Y
3. delete X

6. Show the results (draw a picture) of the following code (assume p, q, and r are node pointers):

p = new node

p.item = "ABC"

p.next = new node

q = p.next

q.item = "abc"

q.next = NULL

r = new node

r.item = "xyz"

r.next = q

p.next = r

7. Write a recursive function that returns the number of occurrences of some specific item in a linked list. State any assumptions made. Give the Big-Oh notation for the function.