#### Lab Quiz Solutions, Data Structures and Algorithms, Week 5 -- Thurs Oct 23 2001

1. Write down the values of these powers:
 a.) 12 b.) 22 e.) 52 f.) 102 g.) 10002 1 4 = 2*2 25 = 5*5 etc. 100 (hundred) 1000000 (million)
These are some data points from the function N2 (squares)

2. Write down the values of these powers:
 a.) 13 b.) 23 e.) 53 f.) 103 g.) 10003 1 8 = 2*2*2 125 = 5*5*5 etc. 1000 (thousand) 1000000000 (billion)
These are some data points from N3 (cubes)

3. Write down the values of these exponents:
 a.) 20 b.) 22 c.) 28 e.) 101 f.) 103 g.) 106 1 4 256 10 1000 1000000
These are some data points from 2N and 10N (exponentials)

4. Write down the values of these logs:
 a.) log21 b.) log24 c.) log2256 e.) log1010 f.) log101000 g.) log101000000 0 2 8 1 3 6
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.) 10N2, N = 10 b.) 0.1N3, N = 10 c.) 10N2, N = 100 d.) 0.1N3, N = 100 1000 = 10 * (10*10) etc. 100 100000 100000

6. Write down the order (Big-O) of these functions of N:
 a.) 10N2 b.) 0.1N3 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. d.) Write down a value of N where b. exceeds a. d.) 101, or any value larger than 100 (see 5c. and 5d.)
Note that b. has the larger order even though a. has larger values at 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 = 100 (obtained by solving a. = b. for N)

7. Write down the order (Big-O) of this code fragment:
```
for (i = 0; i < n; i++)

for (j = 0; 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.