Simple Node.js script for testing yourself on the Big O runtimes of popular data structures (Arrays, Linked List, Queues, AVL Trees, etc...)

big-o-runtimes.js

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

const dataStructureNames = [
  "Array", "Hashmap", "Linked List", "Queue", "Stack", "Graph", "Binary Tree", "AVL Tree", "Min-Max Heap",
  "Skip List", "B Tree"
]

const operations = [
  "Access First Element",
  "Search",
  "Random Insertion",
  "Insertion at Beginning or End",
  "Random Insertion",
  "Deletion",
  "Access First N Elements in Order",
  "Access First Element in Order of X (where X is some sorting order)"
]
const tableData = [
  ["O(1)", "O(N)", "O(1) (or O(N) if in beginning)", "O(N)", "O(N)", "N * O(1)", "O(1)"],
  ["O(1)", "O(1)", "O(1)", "N/A", "O(N)", "O(1)", "O(N)", "O(N)"],
  ["O(1)", "O(N)", "O(N)", "O(1)", "O(N)", "O(N)", "O(N^2)", "O(N)"],
  ["O(1)", "O(N)", "O(N)", "O(1)", "O(N)", "O(N)", "O(N^2) (or O(N) but requires O(N) memory)", "O(N)"],
  ["O(1)", "O(N)", "O(N)", "O(1) (or O(N) if at end)", "O(N)", "O(N)", "O(N^2) (or O(N) but requires O(N) memory)", "O(N)"],
  ["O(1)", "O(N)", "O(1)", "O(1)", "O(N)", "O(1)", "O(N)", "O(N)"],
  ["O(1)", "O(log(N))", "O(log(N))", "O(log(N))", "O(log(N))", "O(log(N))", "N * O(log(N))", "O(log(N))"],
  ["O(1)", "O(log(N))", "O(log(N))", "O(log(N))", "O(log(N))", "O(log(N))", "N * O(log(N))", "O(log(N))"],
  ["O(1)", "O(N)", "O(log(N))", "O(1)", "O(log(N))", "O(log(N))", "N * O(log(N))", "O(1)"],
  ["O(1)", "O(log(N))", "O(log(N))", "O(1)", "O(log(N))", "O(log(N))", "O(N*log(N))", "O(log(N))"],
  ["O(1)", "O(log(N))", "O(log(N))", "O(log(N))", "O(log(N))", "O(log(N))", "O(N*log(N))", "O(log(N))"]
];

function peek() {
  const rowIndex = Math.floor(Math.random() * tableData.length);
  let colIndex = Math.floor(Math.random() * tableData[0].length);
  
  const bigORuntime = tableData[rowIndex][colIndex];
  const dataStructureName = dataStructureNames[rowIndex];
  const operation = operations[colIndex];
  
  return [rowIndex, colIndex, bigORuntime, dataStructureName, operation];
}

const main = async () => {

  const numRows = tableData.length;
  const numCols = tableData[0].length;

  // build a list with all of the numRows * numCols tuples of (rowIndex, colIndex) and then shuffle it

  const allIndices = [];
  for (let i = 0; i < numRows; i++) {
    for (let j = 0; j < numCols; j++) {
      allIndices.push([i, j]);
    }
  }
  // shuffle the array
  for (let i = allIndices.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [allIndices[i], allIndices[j]] = [allIndices[j], allIndices[i]];
  }

  for (const [i, [rowIndex, colIndex]] of allIndices.entries()) {
    const bigORuntime = tableData[rowIndex][colIndex];
    const dataStructureName = dataStructureNames[rowIndex];
    const operation = operations[colIndex];

    console.log(`What is the Big O runtime for ${operation} in a ${dataStructureName}?`);
    
    await new Promise((resolve) => {
      rl.question('Press Enter to see the answer...', () => {
        console.log(`The answer is: ${bigORuntime}\n`);
        resolve();
      });
    });

  }
}

main();