Applet Orchard

Big O Notations

[ad_1]
Get the Code Here:

Welcome to my Big O Notations tutorial. Big O notations are used to measure how well a computer algorithm scales as the amount of data involved increases. It isn’t however always a measure of speed as you’ll see.

This is a rough overview of Big O and I hope to simplify it rather than get into all of the complexity. I’ll specifically cover the following O(1), O(N), O(N^2), O(log N) and O(N log N). Between the video and code below I hope everything is completely understandable.

Posted

in

by

appletorchard

Tags:

Comments

24 responses to “Big O Notations”

  1. Your Mom Avatar
    Your Mom

    I genuinely can't thank you enough for these videos. I started Data Structures and Abstractions today, read the chapter on the Big O, and was completely lost, whereas you made it seem so simple and easy to understand.

    Thank you.

    Reply
  2. Alpha Shuro Avatar
    Alpha Shuro

    I don't know if anyone has already said this but in your final example where you test with array 4, you didn't change the second parameter to pass in the number of items for array 4

    Reply
  3. Tao Pan Avatar
    Tao Pan

    Think about the bubble sort. At least Array.length-1 for loop is needed.
    What if I give you array of (10,9,8,7,6,5,4,3,2,1),the for outer loop is going for 8 times, which is Array.length-2.
    original:10,9,8,7,6,5,4,3,2,1
    If you only run eight time
    9,8,7,6,5,4,3,2,1,10 1st
    8,7,6,5,4,3,2,1,9,10 2nd
    7,6,5,4,3,2,1,8,9,10 3rd
    6,5,4,3,2,1,7,8,9,10 4th
    5,4,3,2,1,6,7,8,9,10 5th
    4,3,2,1,5,6,7,8,9,10 6th
    3,2,1,4,5,6,7,8,9,10 7th
    2,1,3,4,5,6,7,8,9,10 8th

    but you need one more time
    1,2,3,4,5,6,7,8,9,10

    Reply
  4. Tovonn Smith Avatar
    Tovonn Smith

    Sweet video, I should be able to skip a year of computer science because of this alone.

    Reply
  5. The IE Studios Avatar
    The IE Studios

    I want to know if there are some websites or software in order to practice Big-o annotation Analysis, I want something that it gives me a code and ask me for the Big-O annotation. This will be great for practicing.

    If they exist, then it will be great that you can provide me the names or links.

    Thanks in advance.

    Reply
  6. edward Houser Avatar
    edward Houser

    you mentioned that you can find actual code. Where is that?

    Reply
  7. BinaryWorld Avatar
    BinaryWorld

    15:38
    "We have to look at every single elevlvlllvlvvl"

    Reply
  8. Devin M Avatar
    Devin M

    In his bubble sort method, shouldnt his outer for loop have i>0 instead of i>1, otherwise it wont check the element at index 1?

    Reply
  9. Jean-Pierre Hotz Avatar
    Jean-Pierre Hotz

    How do you come up with n log n from log n! (referring to 17:26)? The only way I could think of is the logarithm power rule while assuming that n! = n^n (which can easily be disproven).

    Reply
  10. Konstantinos Saittis Avatar
    Konstantinos Saittis

    I thought binary search works ONLY for sorted arrays but the generateRandomArray() gives you an unsorted array. How can the time given by the binarySearchForValue() be accurate then? Am i missing something?

    Reply
  11. Andres Arizala Avatar
    Andres Arizala

    Thanks for creating this video.

    Reply
  12. Michael Bernardo Avatar
    Michael Bernardo

    Awesome, I learned more about Big O Notations in 20 minutes than I ever did in a term in university.

    Reply
  13. SimonK Avatar
    SimonK

    think I picked your explanation up easier than the one I got at university thanks.

    Reply
  14. ØrChid Avatar
    ØrChid

    Notice how his voice gets deeper throughout the video

    Reply
  15. Mohsin Khan Avatar
    Mohsin Khan

    Watch at 0.75 speed.

    Reply
  16. TarousDT Avatar
    TarousDT

    At the very end you did not change the right value for the quick sort function to Algo3.

    Reply
  17. Umar Khan Avatar
    Umar Khan

    At 4:45 It isn't order of 1 O(1). It should be called O(2) because there are two operations being performed
    1) Assignment of newItem to items[itemsInArray++]. i.e items[itemsInArray++]=newItem.
    2) The variable 'itemsInArray' getting increamented. i.e itemsInArray=itemsInArray+1

    Reply
  18. Thưởng Võ Avatar
    Thưởng Võ

    Link to the code is broken. Could you please fix it?

    Reply
  19. Duarte Santos Avatar
    Duarte Santos

    My teacher should be ashamed and abandon the building.

    Reply
  20. Duarte Santos Avatar
    Duarte Santos

    This guy is not human.

    Reply
  21. Vitamin B Avatar
    Vitamin B

    That's an awesome explanation! Thank you!

    Reply
  22. vaibhav kubre Avatar
    vaibhav kubre

    Replace my professor with you bcoz of your way simpler explanation

    Reply
  23. Dj Sushi Avatar
    Dj Sushi

    If n=10, then 45n^3 = 450^3 and that's equal to 91125000. You have probably a mistake there or I did not understand it.

    Reply
  24. baphnie Avatar
    baphnie

    Minecraft icon lol

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *