CS 302 Practice Problems 1

Try to work these before Tuesday, January 31, 2006.

1. Consider this code fragment. The running time is Theta(log log n). We will eventually use that function, but not for a while. Nevertheless, it comes up surprisingly often.
2. We mentioned "log star" in class. We will eventually use that function, but not for a while. Nevertheless, it comes up surprisingly often. Consider this code fragment. The running time is Theta(log*n).