Big O Notation

By: HackerRank

1767   67   142503

Uploaded on 09/27/2016

Learn about Big O notation, an equation that describes how the run time scales with respect to some input variables. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. http://www.hackerrank.com/domains/tutorials/cracking-the-coding-interview?utm_source=video&utm_medium=youtube&utm_campaign=ctci

Comments (4):

By anonymous    2017-09-20

One of the basic assumptions when calculating BigO is to drop non dominant terms.

Using the first example,

  • Outer Loop has order O(n^2)
  • Inner Loop has order O(n^3)
    • The inner loop independently runs for 'n' times but because it is nested, it will run for 'n * (n^2) '

So, the BigO is of the form O((n^2) + (n^3)) which would suffice to O(n^3).

You can try using the same technique for the second problem.
If you still have some confusion, have a look at the following video: Big O Notation

Original Thread

By anonymous    2017-09-20

Change your targetsFound variable to a set. The reason you use that variable is to look up if a cell has been visited and lookups in lists are slow O(N) time. Sets support fast lookup O(1) and as such should drastically improve your algorithm's performance.

More information about what O(N) and O(1) mean: https://www.youtube.com/watch?v=v4cd1O4zkGw&t=1s

Original Thread

Submit Your Video

If you have some great dev videos to share, please fill out this form.