Fibonacci Heap Degree Bound

Problem

In a Fibonacci heap a node of degree d has subtree size at least F(d + 2), the (d+2)-th Fibonacci number with F(0) = 0 and F(1) = 1. Return the largest possible degree for n >= 1, and 0 when n <= 1.

Hint

Plug small n into F(d + 2) <= n: the largest feasible d is the degree bound.

Test cases

case 1

in: [1]

expected: 0

case 2

in: [4]

expected: 2

case 3

in: [12]

expected: 4

case 4

in: [100]

expected: 9

case 5

in: [1000]

expected: 14

Starter codePython

def fib_heap_degree_bound(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor