[Solved] Given recursive expression, find algorithm with space complexity O(1) [closed]

by


This sequence is Stern’s diatomic sequence, and the function you’ve been given is called fusc(n).

One way to compute it in O(log n) time and O(1) space complexity is to find the n’th value in the Calkin-Wilf tree. That value’s numerator will be fusc(n). You can read some background on the wikipedia page: https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree

Here’s some code that checks the naive fusc implementation with the fast version. It’s in Python, but it would be trivial to convert to C++.

def fusc(n):
    if n < 2:
        return n
    if n%2 == 0:
        return fusc(n//2)
    return fusc(n//2) + fusc(n//2+1)


def fast_fusc(n):
    if n == 0: return 0
    top = 1
    while top <= n:
        top <<= 1
    top >>= 1
    a, b = 1, 1
    while top > 1:
        top >>= 1
        if n & top:
            a, b = a + b, b
        else:
            a, b = a, a + b
    return a


for i in xrange(100):
    assert fusc(i) == fast_fusc(i)

You can see that in fast_fusc, top iterates over the bits of n, so the code performs O(log n) arithmetic operations. There’s only 4 variables used (n, a, b, top) so it uses O(1) space.

solved Given recursive expression, find algorithm with space complexity O(1) [closed]