Fibonacci Number Generator (O(1) Runtime)

This project demonstrates a Fibonacci number generator with O(1) lookup time using a precomputed lookup table approach.

Implementation Overview

The solution uses a precomputed lookup table to achieve constant-time access to Fibonacci numbers:

Key Features:

• O(1) Runtime: Accessing any Fibonacci number takes constant time
• Memory Efficient: Stores only necessary values in memory
• Error Handling: Validates input indices and handles out-of-range requests
• Windows Compatible: Uses Windows system calls for console output

Approach Explanation

Instead of calculating Fibonacci numbers through iteration or recursion (which would be O(n) or O(2^n)), this implementation:

1. Precomputes Fibonacci numbers up to a certain limit (50 numbers in this case)
2. Stores them in a lookup table (array)
3. Provides constant-time access by simply indexing into the array

This approach trades memory for speed - we use more memory to store precomputed values, but achieve O(1) lookup time.

Files Included

1. fibonacci.asm

• AMD64 assembly implementation using Windows syscalls
• Uses lookup table for O(1) access
• Includes Windows API calls for console output

2. fibonacci.nasm

• Alternative NASM version of the Fibonacci generator
• Same functionality as the .asm file but with NASM syntax

3. fibonacci.cpp

• C++ demonstration showing the same lookup table concept
• Easier to compile and run
• Demonstrates O(1) access pattern

How O(1) is Achieved

The O(1) runtime comes from:

1. Precomputation: All Fibonacci numbers are calculated once at compile time
2. Direct Access: The lookup table allows direct indexing without computation
3. Constant Time Operations: Array access in memory takes constant time regardless of index

Usage

To run the C++ version (if you have a compiler):

g++ -o fibonacci.exe fibonacci.cpp
fibonacci.exe

The program will output Fibonacci numbers at various indices, demonstrating that all lookups are O(1) time complexity.

Limitations

• The lookup table is limited to precomputed values (50 in this case)
• For larger indices, a different approach would be needed
• Memory usage increases with the number of precomputed values

This implementation shows how algorithmic design can optimize for specific use cases - trading memory for time complexity when constant-time access is required.