CODEWITHSUNDEEP
javarecursionbig-o
luna
luna

Reputation: 1

Is it possible to calculate Lucas numbers recursively with time complexity O(n)?

I have a homework assignment to calculate Lucas numbers. How can I make my algorithm O(n) while still keeping it recursive?

This is the hint he gives:

When thinking about the question I thought I would keep my main for loop and make it so that it stores the 2 numbers before the one computed but then that would be iterative.

This is my code right now:

lucas(n) {  
    return 2 if n = 0;
    return 1 if n = 1;
    return lucas(n - 1) + lucas(n - 2);
}
main(String args[]) {
    for (int i = 0; i<=10; i++)
        print(lucas(i*5));
}

(The code is written like that in case of plagiarism.)

Upvotes: 0

Views: 684

Answers (3)

hfontanez
hfontanez

Reputation: 6168

I think a Memoized solution for this problem will be O(n) because each solution for n will be calculated no more than one time.

The "trick" is to store the results of lucas(n) in a map so that previously calculated results will be retrieved in constant time O(1) and new values will be calculated once.

(Complete solution needs to compute only if value is not in map)

public class MemoizedLucas {
    private static Map<Integer, Integer> results = new HashMap<>();

    /**
     * @param args
     */
    public static void main(String[] args) {
        // add base cases to map
        results.put(0, 2);
        results.put(1, 1);

        // compute lucas number
        lucas(10);
        System.out.println(results);
    }
    // The lucas function will be called at most 2*n times - O(2*n) is still considered liner time. 
    public static int lucas(int n) {
        
        Integer result = results.get(n);
        if (result != null) return result; // return value if in map

        int a = lucas(n - 1);
        int b = lucas (n - 2);
        results.put(n , a + b);
        return results.get(n);
    }
}

If printed out, the first 10 numbers of the sequence outputted by this program are:

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123

Upvotes: 0

user16320675
user16320675

Reputation: 135

Since this is homework, I will not post the solution as code, but I hope I can show the path to it.

The given hint uses a vector with 2 values - in Java we can use an array (since a method cannot return just two values). The method needs the value of n.

int[] calc(int n) {
    // TODO
}

The formula Gn = M X Gn-1 - M is the given matrix, and Gn = [An , Bn] (An = Ln and Bn = Ln-1) - can we rewritten as
[An , Bn] = [[1,1] [1,0]] X [An-1 , Bn-1] or

An = 1*An-1 + 1*Bn-1 = An-1 + Bn-1 and
Bn = 1*An-1 + 0*Bn-1 = An-1

The method would call itself with n-1, unless n == 0, to get [An-1,Bn-1] and then calculate the output array [An,Bn] using above formula.

Initial array, for n=0, should be [2,-1] (aka G0 in hint.)

(since Gn only depends on Gn-1 the pure recursive solution is O(n) - unlike the usual method to calculate the Lucas number where Ln depends on Ln-1 and Ln-2)

I have completely ignored the second hint and used int[] above - but don't forget to consider if an int will be able to represent L500
(having the hint is a sign that it will not)

Upvotes: 1

Joop Eggen
Joop Eggen

Reputation: 109577

The hint is to define a recursive G function, and take on of both Lucas values for the G result. The lucas function can then be defined as call to G.

As you see, G is O(N).

int lucas(int n) { return g(n)[0]; }
int[] g(int n) { ... recursiveG ... }

Upvotes: 0

Related Questions