Evaluate speed of Algorithms and Data Structures using Big O notation

function sayHiNTimes(n) {
  for (let i = 0; i < n; i++) {
    console.log('hi');
  }
}

function printAllItems(items) {
  items.forEach(item => {
    console.log(item);
  });
}

So sometimes n is an actual number that’s an input to our function, and other times n is the number of items in an input array (or an input map, or an input object, etc.).

function printAllNumbersThenAllPairSums(numbers) {

  console.log('these are the numbers:');
  numbers.forEach(number => {
    console.log(number);
  });

  console.log('and these are their sums:');
  numbers.forEach(firstNumber => {
    numbers.forEach(secondNumber => {
      console.log(firstNumber + secondNumber);
    });
  });
}

function sayHiNTimes(n) {
  for (let i = 0; i < n; i++) {
    console.log('hi');
  }
}

function arrayOfHiNTimes(n) {
  const hiArray = [];
  for (let i = 0; i < n; i++) {
    hiArray[i] = 'hi';
  }
  return hiArray;
}

Usually when we talk about space complexity, we’re talking about additional space, so we don’t include space taken up by the inputs. For example, this function takes constant space even though the input has n items:

function getLargestItem(items) {
  let largest = -Number.MAX_VALUE;
  items.forEach(item => {
    if (item > largest) {
      largest = item;
    }
  });
  return largest;
}

Sometimes there’s a tradeoff between saving time and saving space, so you have to decide which one you’re optimizing for.

Big O analysis is awesome except when it’s not

You should make a habit of thinking about the time and space complexity of algorithms as you design them. Before long this’ll become second nature, allowing you to see optimizations and potential performance issues right away.

Asymptotic analysis is a powerful tool, but wield it wisely.

Big O ignores constants, but sometimes the constants matter. If we have a script that takes 5 hours to run, an optimization that divides the runtime by 5 might not affect big O, but it still saves you 4 hours of waiting.

Beware of premature optimization. Sometimes optimizing time or space negatively impacts readability or coding time. For a young startup it might be more important to write code that’s easy to ship quickly or easy to understand later, even if this means it’s less time and space efficient than it could be.

But that doesn’t mean startups don’t care about big O analysis. A great engineer (startup or otherwise) knows how to strike the right balance between runtime, space, implementation time, maintainability, and readability.

You should develop the skill to see time and space optimizations, as well as the wisdom to judge if those optimizations are worthwhile.

As a newer developer understand that we generally always side with readability and maintainability over speed and space concerns because cpu speed and memory are so abundant. When we start to notice issues in the cpu profiler then we use the profiler to determine which functions are causing the issue and optimize either the functions that call them or the functions themselves. If you see a way to dramatically lower the Big O runtime it is ok to implement that solution if the code is still highly readable and maintainable, but make writing code that is easy to work on a priority as this can dramatically effect the cost of implementing new code later.

You may find that the simple yet elegant solution that is maintainable and readable is also space and runtime efficient.

function sayHiManyTimes(n) {
  const hiArray = [];
  for (let i = 0; i < n; i++) {
    for (let i = 0; i < n; i++) {
      hiArray[i] = 'hi';
    }
  }
  return hiArray;
}

Hint: What function from up above has nested loops too?

Video Link

Here is a video that helps cement some of the concepts that you are learning.  You are welcome to review it if you need another perspective on Big O notation to help clarify things.