Links

̶
Adam I. Gerard
ISU
NIU
CS MS TBD

Time Complexity Examples

Simple example demonstrating the speed of O(N²), O(N), O(log(N)), O(1) empirically.

  • Difficulty: Easy
  • Kind: Basic Concepts
  • Platform: Basic Concepts
  • Solved: N/A
  • Time Complexity: O(N²), O(N), O(log(N)), O(1)
  • Space Complexity: O(1)
  • Answer Rank: Top N/A

Insights

We observe how much faster Constant and Linear time complexity-bound algorithms are than Quadratic-bounded ones.
// ES5 compliant.
window.onload = function () {

    var quadratic = function() {
    var BEGIN = new Date();
    for (let i = 0; i < 10000; i++) {
      for (let j = 0; j < 10000; j++) {
      }
    }
    var END = new Date();
    print_console(`Time taken: ${END - BEGIN}`, 'quadratic');
  };

  var linear = function() {
    const BEGIN = new Date();
    for (let i = 0; i < 100000; i++) {}
    const END = new Date();
    print_console(`Time taken: ${END - BEGIN}`, 'linear');
  };

  var logarithimic = function() {
    const BEGIN = new Date();
    for (let i = 0; i < 100000; i++) {
      for (let j = 0; j < 100000; j++) {
        j = j * 2;
      }
    }
    var END = new Date();
    print_console(`Time taken: ${END - BEGIN}`, 'logarithimic');
  };

  var constant =function() {
    var BEGIN = new Date();
    var END = new Date();
    print_console(`Time taken: ${END - BEGIN}`, 'constant');
  };

  quadratic();
  linear();
  logarithimic();
  constant();
};

Test Cases

      Links