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 N²
   
   
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 N³
   
   
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 2^N and 10^N
   
   
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 log_bx = y means b^y = 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(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.