Code for computing fib numbers in log time
- User
Code for computing fib numbers in log time
Assistant
def fib_log_time(n): """Computes the nth Fibonacci number in log time. Args: n: The index of the Fibonacci number to compute. Returns: The nth Fibonacci number. """ # Base cases if n == 0: return 0 if n == 1: return 1 # Compute the Fibonacci numbers of the two halves of n. k = n // 2 f_k = fib_log_time(k) f_k_plus_1 = fib_log_time(k + 1) # Compute the nth Fibonacci number using the matrix multiplication formula. return f_k * f_k_plus_1 + f_k_plus_1 * f_k_plus_1 # Example usage n = 10 result = fib_log_time(n) print(f"The {n}th Fibonacci number is {result}")The time complexity of this algorithm is O(log n), which is significantly faster than the naive recursive algorithm, which has a time complexity of O(2^n). This is because the recursive calls are made on the two halves of n, rather than the entire number. As a result, the number of recursive calls is reduced by a factor of 2 at each level of the recursion, leading to a logarithmic time complexity.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.