# 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.