#### Lab Quiz Solutions, Data Structures and Algorithms, Week 4 -- Tues Oct 16 2001

1. Write down the values of these powers:
 a.) 12 b.) 22 c.) 32 d.) 42 e.) 52 f.) 102 g.) 1002 1 4 = 2*2 9 = 3*3 etc. 16 25 100 10000
These are some data points from the function N2

2. Write down the values of these powers:
 a.) 13 b.) 23 c.) 33 d.) 43 e.) 53 f.) 103 g.) 1003 1 8 = 2*2*2 27 = 3*3*3 etc. 64 125 1000 1000000
These are some data points from N3

3. Write down the values of these exponents:
 a.) 21 b.) 22 c.) 23 d.) 24 e.) 101 f.) 102 g.) 103 2 4 = 2*2 8 = 2*2*2 etc. 16 10 100 1000
These are some data points from 2N and 10N

4. Write down the values of these logs:
 a.) log22 b.) log24 c.) log28 d.) log216 e.) log1010 f.) log10100 g.) log101000 1 2 3 4 1 2 3
Note the relation between questions 3 and 4, because logbx = y means by = x

5. Write down the values of these functions of N for the specified values of N:
 a.) 100N2, N = 10 b.) 0.01N3, N = 10 c.) 100N2, N = 100 d.) 0.01N3, N = 100 10000 = 100 * (10*10) etc. 10 1000000 10000

6. Write down the order (Big-O) of these functions of N:
 a.) 100N2 b.) 0.01N3 c.) Which has the larger order, a. or b. ? O(N2) O(N3) b. has the larger order because N3 is a higher power than N2.
Note that b. has the larger order even though a. has larger values at N = 10 and N = 100. We say b. has the larger order because the values of b. will exceed values of a. when N becomes sufficiently large. The crossover point where b. begins to exceed a. occurs when N = 10000 (obtained by solving a. = b. for N)

7. Write down the order (Big-O) of this code fragment:

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

sum = sum + a[i]

O(N), also called linear or first-order. This code is O(N) because it just has a single loop, so the execution time is proportional to n.

8. Write down the order (Big-O) of this code fragment:

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

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

sum = sum + a[i]*b[j]

O(N2), also called squared or quadratic. This code is O(N2) because it has two nested loops, so the execution time is proportional to n squared -- the body of the inner loop is executed (up to) n times each time the body of the outer loop is executed.