Practice Labs

Complexity Exercises

Exercise 1

  • Write a tester program that counts and displays the number of iterations of the following loop:

while problemSize > 0:
    problemSize = problemSize // 2

Exercise 2

  • Run the program you created in Exercise 1 using problem sizes, of 1000, 2000, 4000, 10,000, and 100,000. As the problem size doubles or increases by a factor of 10.
    What happens to the number iterations?

Exercise 3

  • The difference between the results of two calls of the functions time.time() is an elapsed time. Because the operating system might use the CPU for part of this time, the elapsed time might not reflect the actual time that a Python code segment uses the CPU. Browse the Python documention for an alternative way of recording the processing time, and describe how this would be done.

Exercise 4

  • Assume that each of the following expressions indicates the number of operations performed by an algorithm for a problem size of n. Point out the dominant term of each algorithm and use big-O notation to classify it. 

    a. 2^n - 4n^2 + 5n
    b. 3n^2 + 6
    c. n^3 + n^2 - n

Exercise 5

  • For problem size n, algorithms A and B perform n^2 and (1/2)n^2 + (1/2)n instructions, respectively. Which algorithm does more work? Are there particular problem sizes for which one algorithm performs significantly better than the other? Are there particular problem sizes for which both algorithms perform approximately the same amount of work?

Exercises 6

  • At what point does an n^4 algorithm begin to perform better than a 2^n algorithm?

Sort Exercises

  • Describe the strategy of quicksort and explain why it can reduce the time complexity of sorting from O(n2) to O(n log n).

  • Why is quicksort not O(n log n) in all cases? Describe the worst-case situation for quicksort and give a list of 10 integers, 1- 10, that would produce this behavior.

  • The partition operation in quicksort chooses the item at the midpoint as the pivot. Describe two other strategies for selecting a pivot value.

  • Sandra has a bright idea: when the length of a sublist in quicksort is less than a certain number - say, 30 elements - run an insertion sort to process that sublist.
    Explain why this is a bright idea.

  • Why is merge sort an O(n log n) algorithm in the worst case?