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 N² (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 N³ (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 2^N and 10^N (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 log_bx = y means b^y = 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(N²), also called squared or quadratic. This code is O(N²) 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.