[go: up one dir, main page]
Scribd
Upload
4 views1 page

1 Fib

The document provides implementations of both iterative and recursive methods to calculate Fibonacci numbers. The iterative approach has a time complexity of O(n) and a space complexity of O(1), while the recursive approach has a time complexity of O(2^n) and a space complexity of O(n). Example usages of both methods are included to demonstrate their functionality.

Uploaded by

shinchansbv
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
4 views1 page

1 Fib

The document provides implementations of both iterative and recursive methods to calculate Fibonacci numbers. The iterative approach has a time complexity of O(n) and a space complexity of O(1), while the recursive approach has a time complexity of O(2^n) and a space complexity of O(n). Example usages of both methods are included to demonstrate their functionality.

Uploaded by

shinchansbv
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 1

# Write a program non-recursive and recursive program to calculate

# Fibonacci numbers and analyze their time and space complexity

def fibonacci_iterative(n):
"""Calculate the nth Fibonacci number using an iterative approach."""
if n <= 0:
return 0
elif n == 1:
return 1

a, b = 0, 1 # Initialize the first two Fibonacci numbers


for _ in range(2, n + 1):
a, b = b, a + b # Shift values to generate the next Fibonacci number
return b

# Example usage:
n = 10
print(f"Iterative Fibonacci({n}) = {fibonacci_iterative(n)}")

# Time and Space Complexity Analysis (Iterative)


# Time Complexity:
# O(n) � Since the loop runs n times, the time required is linear in terms of n.
# Space Complexity:
# O(1) � Only a fixed amount of extra space is used, regardless of n.

def fibonacci_recursive(n):
"""Calculate the nth Fibonacci number using a recursive approach."""
if n <= 0:
return 0
elif n == 1:
return 1
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Example usage:
n = 10
print(f"Recursive Fibonacci({n}) = {fibonacci_recursive(n)}")

# Time and Space Complexity Analysis (Recursive)


# Time Complexity:
# O(2^n) � Each function call spawns two additional recursive calls, resulting in
an exponential number of calls.
# Space Complexity:
# O(n) � The maximum depth of the recursion tree is n. Each recursive call uses
stack space.

You might also like