Algorithms Homework 9



Homework 9

1. Describe a divide-and-conquer algorithm that accepts a positive integer
n and computes blg nc (that is, the largest integer x such that 2x ≤ n).
Your algorithm should take O(lg(lg n)) time.
Hint: you may wish to base your approach on one-sided binary search,
which starts at 1, doubles the value until it becomes too large, then performs binary search between the last value that worked and the first value
that failed. (Divide-and-conquer algorithms aren’t required to be recursive.) You may assume that the square root function takes Θ(1) time,
though there is an O(lg lg n) algorithm that does not use the square root.


There are no reviews yet.

Be the first to review “Algorithms Homework 9”

Your email address will not be published.