Basic space/time complexity implementations

space-constant.js

// Exercise 4: O(1) Space - Constant Memory
// Finding the largest number WITHOUT creating new arrays

// Test data
const small = [3, 1, 4, 1, 5, 9, 2];
const medium = Array.from({length: 100}, () => Math.floor(Math.random() * 1000));
const large = Array.from({length: 10000}, () => Math.floor(Math.random() * 1000));

// O(1) space function - only uses a few variables
function findLargest(arr) {
    // These variables don't grow with input size
    let largest = arr[0];        // 1 variable
    let operations = 0;          // 1 variable
    let currentIndex = 1;        // 1 variable

    // Loop through array
    while (currentIndex < arr.length) {
        operations++;

        if (arr[currentIndex] > largest) {
            largest = arr[currentIndex];
        }

        currentIndex++;
    }

    return {
        largest: largest,
        operations: operations,
        variablesUsed: 3  // largest, operations, currentIndex
    };
}

// Test with different sizes
console.log("=== O(1) SPACE COMPLEXITY DEMO ===");
console.log("Finding largest number using constant memory...\n");

console.log("Small array (7 elements):");
const result1 = findLargest(small);
console.log(`Largest: ${result1.largest}`);
console.log(`Operations: ${result1.operations}`);
console.log(`Variables used: ${result1.variablesUsed}`);

console.log("\nMedium array (100 elements):");
const result2 = findLargest(medium);
console.log(`Largest: ${result2.largest}`);
console.log(`Operations: ${result2.operations}`);
console.log(`Variables used: ${result2.variablesUsed}`);

console.log("\nLarge array (10,000 elements):");
const result3 = findLargest(large);
console.log(`Largest: ${result3.largest}`);
console.log(`Operations: ${result3.operations}`);
console.log(`Variables used: ${result3.variablesUsed}`);

console.log("\n💡 Notice: We always use exactly 3 variables!");
console.log("No matter how big the input gets, memory usage stays the same.");
console.log("This is O(1) space complexity - constant memory usage.");

space-linear.js

// Exercise 5: O(n) Space - Linear Memory
// Creating a copy of an array with all numbers doubled

// Test data
const small = [1, 2, 3, 4, 5];
const medium = Array.from({length: 100}, (_, i) => i + 1);
const large = Array.from({length: 1000}, (_, i) => i + 1);

// O(n) space function - creates new array same size as input
function doubleNumbers(arr) {
    let operations = 0;

    // Create new array - this uses O(n) space!
    let doubledArray = [];

    for (let i = 0; i < arr.length; i++) {
        operations++;
        doubledArray.push(arr[i] * 2);  // Adding to new array
    }

    return {
        originalArray: arr,
        doubledArray: doubledArray,
        operations: operations,
        originalSize: arr.length,
        newArraySize: doubledArray.length,
        totalMemoryUsed: arr.length + doubledArray.length  // Input + Output
    };
}

// Test with different sizes
console.log("=== O(n) SPACE COMPLEXITY DEMO ===");
console.log("Creating doubled arrays (new memory for each)...\n");

console.log("Small array (5 elements):");
const result1 = doubleNumbers(small);
console.log(`Original: [${result1.originalArray.join(', ')}]`);
console.log(`Doubled:  [${result1.doubledArray.join(', ')}]`);
console.log(`Memory used: ${result1.totalMemoryUsed} array slots`);

console.log("\nMedium array (100 elements):");
const result2 = doubleNumbers(medium);
console.log(`Original size: ${result2.originalSize}`);
console.log(`New array size: ${result2.newArraySize}`);
console.log(`Memory used: ${result2.totalMemoryUsed} array slots`);

console.log("\nLarge array (1000 elements):");
const result3 = doubleNumbers(large);
console.log(`Original size: ${result3.originalSize}`);
console.log(`New array size: ${result3.newArraySize}`);
console.log(`Memory used: ${result3.totalMemoryUsed} array slots`);

console.log("\n💡 Notice: Memory usage grows with input size!");
console.log("Input size 1000 = Memory usage 2000 (original + new array)");
console.log("This is O(n) space complexity - linear memory growth.");
console.log("\n🤔 Compare this to Exercise 4 where memory stayed constant!");

time-constant.js

// Exercise 1: O(1) - Constant Time
// Getting the first element of an array

// Test data - different sizes
const small = [1, 2, 3, 4, 5];
const medium = Array.from({length: 100}, (_, i) => i + 1);
const large = Array.from({length: 10000}, (_, i) => i + 1);

// O(1) function - always takes the same time
function getFirstElement(arr) {
    let operations = 0;

    operations++; // This is our "step" - accessing arr[0]
    return {
        value: arr[0],
        operations: operations
    };
}

// Test with different sizes
console.log("=== O(1) CONSTANT TIME DEMO ===");
console.log("Getting first element from arrays of different sizes...\n");

console.log("Small array (5 elements):");
const result1 = getFirstElement(small);
console.log(`First element: ${result1.value}, Operations: ${result1.operations}`);

console.log("\nMedium array (100 elements):");
const result2 = getFirstElement(medium);
console.log(`First element: ${result2.value}, Operations: ${result2.operations}`);

console.log("\nLarge array (10,000 elements):");
const result3 = getFirstElement(large);
console.log(`First element: ${result3.value}, Operations: ${result3.operations}`);

console.log("\n💡 Notice: No matter how big the array gets, we always do exactly 1 operation!");
console.log("This is O(1) - constant time complexity.");

time-linear.js

// Exercise 2: O(n) - Linear Time
// Finding a specific number in an array

// Test data
const small = [1, 2, 3, 4, 5];
const medium = Array.from({length: 100}, (_, i) => i + 1);
const large = Array.from({length: 1000}, (_, i) => i + 1);

// O(n) function - time grows with input size
function findNumber(arr, target) {
    let operations = 0;

    for (let i = 0; i < arr.length; i++) {
        operations++; // Each comparison is an operation

        if (arr[i] === target) {
            return {
                found: true,
                position: i,
                operations: operations
            };
        }
    }

    return {
        found: false,
        position: -1,
        operations: operations
    };
}

// Test with different sizes - looking for the LAST element (worst case)
console.log("=== O(n) LINEAR TIME DEMO ===");
console.log("Searching for the LAST element in arrays (worst case)...\n");

console.log("Small array (5 elements) - looking for 5:");
const result1 = findNumber(small, 5);
console.log(`Found: ${result1.found}, Position: ${result1.position}, Operations: ${result1.operations}`);

console.log("\nMedium array (100 elements) - looking for 76:");
const result2 = findNumber(medium, 76);
console.log(`Found: ${result2.found}, Position: ${result2.position}, Operations: ${result2.operations}`);

console.log("\nLarge array (1000 elements) - looking for 423:");
const result3 = findNumber(large, 423);
console.log(`Found: ${result3.found}, Position: ${result3.position}, Operations: ${result3.operations}`);

console.log("\nLarge array (1000 elements) - looking for 1000:");
const result4 = findNumber(large, 1000);
console.log(`Found: ${result4.found}, Position: ${result4.position}, Operations: ${result4.operations}`);

console.log("\n💡 Notice: Operations = Array Size!");
console.log("When array is 2x bigger, operations are 2x more.");
console.log("This is O(n) - linear time complexity.");

time-logarithmic.js

// Exercise 7: O(log n) - Logarithmic Time
// Binary Search - Like finding a word in a dictionary!

// Test data - MUST be sorted for binary search to work
const small = [1, 3, 5, 7, 9, 11, 13, 15];  // 8 elements
const medium = Array.from({length: 100}, (_, i) => i * 2 + 1);  // 100 odd numbers
const large = Array.from({length: 1000}, (_, i) => i * 2 + 1);  // 1000 odd numbers
const extraLarge = Array.from({length: 100000}, (_, i) => i * 2 + 1);  // 10,000 odd numbers

// O(log n) Binary Search - cuts problem in half each time!
function binarySearch(sortedArray, target) {
    let operations = 0;
    let left = 0;
    let right = sortedArray.length - 1;
    let steps = [];  // Track our search steps

    while (left <= right) {
        operations++;
        let middle = Math.floor((left + right) / 2);
        let middleValue = sortedArray[middle];

        steps.push({
            step: operations,
            left: left,
            right: right,
            middle: middle,
            middleValue: middleValue,
            searchSpace: right - left + 1
        });

        if (middleValue === target) {
            return {
                found: true,
                position: middle,
                operations: operations,
                steps: steps
            };
        } else if (middleValue < target) {
            left = middle + 1;  // Search right half
        } else {
            right = middle - 1; // Search left half
        }
    }

    return {
        found: false,
        position: -1,
        operations: operations,
        steps: steps
    };
}

// Compare with linear search for context
function linearSearch(array, target) {
    let operations = 0;
    for (let i = 0; i < array.length; i++) {
        operations++;
        if (array[i] === target) {
            return { found: true, position: i, operations: operations };
        }
    }
    return { found: false, position: -1, operations: operations };
}

console.log("=== O(log n) LOGARITHMIC TIME DEMO ===");
console.log("Binary Search vs Linear Search - The Dictionary Method!\n");

// Test with different sizes - looking for element near the end
console.log("🔍 Small array (8 elements) - looking for 13:");
const target1 = 13;
const binaryResult1 = binarySearch(small, target1);
const linearResult1 = linearSearch(small, target1);
console.log(`Binary Search: ${binaryResult1.operations} operations`);
console.log(`Linear Search: ${linearResult1.operations} operations`);
console.log(`Search steps: ${binaryResult1.steps.map(s => s.middleValue).join(' → ')}\n`);

console.log("🔍 Medium array (100 elements) - looking for 151:");
const target2 = 151;
const binaryResult2 = binarySearch(medium, target2);
const linearResult2 = linearSearch(medium, target2);
console.log(`Binary Search: ${binaryResult2.operations} operations`);
console.log(`Linear Search: ${linearResult2.operations} operations`);

console.log("🔍 Large array (1,000 elements) - looking for 1501:");
const target3 = 1501;
const binaryResult3 = binarySearch(large, target3);
const linearResult3 = linearSearch(large, target3);
console.log(`Binary Search: ${binaryResult3.operations} operations`);
console.log(`Linear Search: ${linearResult3.operations} operations`);

console.log("🔍 Extra Large array (10,000 elements) - looking for 15001:");
const target4 = 15001;
const binaryResult4 = binarySearch(extraLarge, target4);
const linearResult4 = linearSearch(extraLarge, target4);
console.log(`Binary Search: ${binaryResult4.operations} operations`);
console.log(`Linear Search: ${linearResult4.operations} operations`);

console.log("\n" + "=".repeat(60));
console.log("📊 COMPARISON TABLE:");
console.log("Array Size  | Binary O(log n) | Linear O(n)  | Improvement");
console.log("------------|-----------------|--------------|------------");
console.log(`      8     |       ${binaryResult1.operations}         |      ${linearResult1.operations}       |     ${Math.round(linearResult1.operations/binaryResult1.operations)}x faster`);
console.log(`    100     |       ${binaryResult2.operations}         |     ${linearResult2.operations}      |    ${Math.round(linearResult2.operations/binaryResult2.operations)}x faster`);
console.log(`  1,000     |      ${binaryResult3.operations}         |    ${linearResult3.operations}     |   ${Math.round(linearResult3.operations/binaryResult3.operations)}x faster`);
console.log(`10,000     |      ${binaryResult4.operations}         |  ${linearResult4.operations.toLocaleString()}   |  ${Math.round(linearResult4.operations/binaryResult4.operations)}x faster`);

console.log("\n💡 Key Insights:");
console.log("📚 Like finding a word in dictionary - you don't start from 'A'!");
console.log("✂️  Each step cuts the problem IN HALF");
console.log("🚀 10,000 elements? Only ~14 steps max!");
console.log("📈 As data grows 10x, steps grow by only ~3");

console.log("\n🎯 The Magic of O(log n):");
console.log("Even with MASSIVE datasets, search stays lightning fast!");
console.log("This is why databases and search engines use logarithmic algorithms.");

time-quadratic.js

// Exercise 3: O(n²) - Quadratic Time
// Finding all pairs of numbers that add up to a target

// Test data
const small = [1, 2, 3, 4, 5];
const medium = Array.from({length: 50}, (_, i) => i + 1);
const large = Array.from({length: 100}, (_, i) => i + 1);

// O(n²) function - nested loops!
function findPairsThatSum(arr, targetSum) {
    let operations = 0;
    let pairs = [];

    // Outer loop
    for (let i = 0; i < arr.length; i++) {
        // Inner loop - this creates the n² complexity!
        for (let j = i + 1; j < arr.length; j++) {
            operations++; // Each comparison is an operation

            if (arr[i] + arr[j] === targetSum) {
                pairs.push([arr[i], arr[j]]);
            }
        }
    }

    return {
        pairs: pairs,
        operations: operations,
        totalPairs: pairs.length
    };
}

// Test with different sizes
console.log("=== O(n²) QUADRATIC TIME DEMO ===");
console.log("Finding all pairs that sum to 7...\n");

console.log("Small array (5 elements):");
const result1 = findPairsThatSum(small, 7);
console.log(`Pairs found: ${result1.totalPairs}, Operations: ${result1.operations}`);
console.log(`Expected operations: 5² = ${5 * 5} (roughly)`);

console.log("\nMedium array (50 elements):");
const result2 = findPairsThatSum(medium, 7);
console.log(`Pairs found: ${result2.totalPairs}, Operations: ${result2.operations}`);
console.log(`Expected operations: 50² = ${50 * 50} (roughly)`);

console.log("\nLarge array (100 elements):");
const result3 = findPairsThatSum(large, 7);
console.log(`Pairs found: ${result3.totalPairs}, Operations: ${result3.operations}`);
console.log(`Expected operations: 100² = ${100 * 100} (roughly)`);

console.log("\n😱 Notice: When array doubles from 50 to 100...");
console.log("Operations roughly QUADRUPLE!");
console.log("This is O(n²) - quadratic time complexity.");
console.log("Nested loops are dangerous for large data!");