What is Big O Notation?

Jonathan Rasmusson
A free video tutorial from Jonathan Rasmusson
Ex-Spotify Engineer, The Agile Samurai
4.4 instructor rating • 5 courses • 41,631 students

Learn more from the full course

Data Structures and Algorithms Bootcamp

How to ace your Silicon Valley style coding interview

06:27:06 of on-demand video • Updated October 2020

  • How to answer commonly asked Silicon Valley style interview questions
  • Demonstrate knowledge and mastery of data structures and algorithms
  • How to pass Silicon Valley style technical interviews
  • Interview confidently
  • Land your dream job
English Hello and welcome back. Have you ever been asked to describe the runtime complexity of adding an element to the back of a linked list. Or how about describing the runtime characteristics of a Fibonacci series These may or may not have come up at your last cocktail party, but believe it or not these are some commonly asked interview questions from many companies in the valley. And while they may sound Greek to you and me and this section you're going to learn to speak a new language not a computer language but a language computer scientists and engineers used to describe efficiency or runtime characteristics of their programs. And by the end of this section not only will you be able to speak this new language, you'll be able to use it to describe the characteristics of your own algorithms something called Big O notation. So what is this thing called big O notation. Why is it use so much in our industry. Big O notation also known as time complexity, is basically a measure of the efficiency of an algorithm. It's used all the time in the industry because early on computer scientists and engineers needed ways to compare algorithms which were faster which were quicker and which are more efficient. And Big-O notation is something that came out of the academic world to describe the different runtime characteristics of all the data structures and algorithms that we use everyday when we're writing programs. Now we've already touched on Big-O notation for example when we looked at arrays we realize that random access to an array was something that was really a killer feature. It was super fast. We call that constant time in Big-O notation. That's O to the one. Likewise any time we had to walk through an array do some looping and do some iterating, In other words where the number of elements in our data structure increased and the operation took longer we call that linear time. An example of that would be deleting the value from a linked list. So Big-O notation is used to describe these runtime characteristics. And it's important to know because when you get into your interview a very commonly asked question or something you may be asked to do is actually describe the runtime characteristic of the algorithm you develop on the white board on paper or in code. In the interview. So that's why it's really important we start to get more and more familiar with this language with this notation and really understand what it means and how to apply it effectively in your interview.