Problem Three: Hybrid RMQ Structures Let's begin with some new notation For any k 20. let's define the function log) n to be the function log log log logn (k times) For example: logn=n log") n = log n log2 n = log log n log n = log log logn This question explores these sorts of repeated logarithms in the context of range minimum queries. i. Using the hybrid framework, show that that for any fixed k 2 1, there is an RMQ data structure with time complexity (O(n logn). O(1)). For notational simplicity, we'll refer to the kth of these structures as Dk. (Yes, we know that the Fischer-Heun structure is a (O(n). O(1)) solution to RMQ and therefore technically meets these requirements. But for the purposes of this question, let's imagine that you didn't know that such a structure existed and were instead curious to see how fast an RMQ struc- ture you could make without resorting to the Method of Four Russians. e) ii. Although for each fixed k the Dx data structure has query time 0(1), the query times on the Dk structures will increase as k increases. Explain why this is the case and why this doesn't contradict your result from part (1) (The rest of this section is just for fun) The iterated logarithm function, denoted log* n, is defined as follows: log* nis the smallest natural number k for which logns1 Intuitively, log* n measures the number of times that you have to take the logarithm of n before n drops to one. For example: log* 1 = 0 log* 2 = 1 log* 4 = 2 logt 16 = 3 log* 65,536 = 4 log* 265.536 = 5 This function grows extremely slowly. For reference, the number of atoms in the universe is estimated to be about 1090 2240 and from the values above you can see that log* 100 is 5. For arrays of length n. the data structure Deg is an (O(n log* n). O log* n)) solution to RMQ. Given that log* n is, practically speaking a constant, that makes for a fast RMQ data structure! Problem Three: Hybrid RMQ Structures Let's begin with some new notation For any k 20. let's define the function log) n to be the function log log log logn (k times) For example: logn=n log") n = log n log2 n = log log n log n = log log logn This question explores these sorts of repeated logarithms in the context of range minimum queries. i. Using the hybrid framework, show that that for any fixed k 2 1, there is an RMQ data structure with time complexity (O(n logn). O(1)). For notational simplicity, we'll refer to the kth of these structures as Dk. (Yes, we know that the Fischer-Heun structure is a (O(n). O(1)) solution to RMQ and therefore technically meets these requirements. But for the purposes of this question, let's imagine that you didn't know that such a structure existed and were instead curious to see how fast an RMQ struc- ture you could make without resorting to the Method of Four Russians. e) ii. Although for each fixed k the Dx data structure has query time 0(1), the query times on the Dk structures will increase as k increases. Explain why this is the case and why this doesn't contradict your result from part (1) (The rest of this section is just for fun) The iterated logarithm function, denoted log* n, is defined as follows: log* nis the smallest natural number k for which logns1 Intuitively, log* n measures the number of times that you have to take the logarithm of n before n drops to one. For example: log* 1 = 0 log* 2 = 1 log* 4 = 2 logt 16 = 3 log* 65,536 = 4 log* 265.536 = 5 This function grows extremely slowly. For reference, the number of atoms in the universe is estimated to be about 1090 2240 and from the values above you can see that log* 100 is 5. For arrays of length n. the data structure Deg is an (O(n log* n). O log* n)) solution to RMQ. Given that log* n is, practically speaking a constant, that makes for a fast RMQ data structure
