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.