On 1/3/06, pramod <[EMAIL PROTECTED]> wrote: > The problem is not clear to me. How can an algo exist that takes O(n) > space but only O(log n) time? O(n) space for precalculation O(log n) time for real computation
> Even just to access the O(n) memory, we > need O(n) time. For example in the above algo, if i = 1 and j = n, then > how can the sum be obtained in O(log n) time? re-read the previous posts ... The problem is not really, really, really clear, in fact I tried to solve the problem: ----------------- Given sorted array of size n. For any i, j < n; return me sum from array[i] to array[j] in a maximum time of O(log n). You can do pre-computations, using O(n) memory for any kind of data-structure. Pre-computations computational time is not important. ----------------- bye ! mattia.
