4. Suppose we use the sequence of integers of the form 2P39, where p, q≥ 0, for Shell-sorting an array of n ≥ 1 elements. Moreover, the sequence contains all integers of the form 2P39 that are strictly less than n. (a) Suppose q* is the largest (integer) exponent such that 39* <n. Justify that there are at most (q*+2) (q*+1) integers in the sequence. (Hint: The "triangle" of integers of the form 2P39 contains q* + 1 integers at the row that includes 39". What is the maximum number of integers in the next row that could be included in the sequence? How about the row after that?) (b) Suppose p* is the largest (integer) exponent such that 2P* q*. For the row that contains the integer 2P", what is the maximum number of integers that could be included in the sequence? How about the row above that?)

Home
questions and answers
4 suppose we use the sequence of integers of the form 2p39 where p q 0

Search for questionUpload Image

Question

4. Suppose we use the sequence of integers of the form 2P39, where p, q≥ 0, for Shell-sorting an array of n ≥ 1 elements. Moreover, the sequence contains all integers

of the form 2P39 that are strictly less than n. (a) Suppose q* is the largest (integer) exponent such that 39* q*. For the row that contains the integer 2P", what is the maximum number of integers that could be included in the sequence? How about the row above that?)