Introduction to Big O Notation and Time Complexity (Data Structures & Algorithms #7)

Introduction to Big O Notation and Time Complexity (Data Structures & Algorithms #7)


Hey everyone. In this video, I’m going to give you an introduction to Big O notation and time complexity. These concepts basically give you one way of describing how the time it takes to run your function grows as the size of the input grows. To see what I mean by that exactly, let’s take a look at a few examples here. First of all, let’s say you are given an array like this and let’s say that this array could be of any lengths. It could be one hundred elements long, a thousand elements long or even one hundred thousand elements. And let’s say you want to write a function that takes this array and returns the sum of all the numbers in this array. So, in your function you wanna add up all the numbers of this array and returns the sum. And that function might look like this function right here and I’m gonna use pseudocode here to write this function. So, first of all let’s define our function that gonna be called find sum which is going to take given array as input and then inside this function first of all we gonna initialize a variable called total to 0 and then for each i in this given array or for each number total to 0

100 thoughts on “Introduction to Big O Notation and Time Complexity (Data Structures & Algorithms #7)”

  1. Ufuk Kayserilioglu

    The last example is not quite correct. Finding the sum of the 2D array is still a linear time operation with respect to the size of your input. It is just that the size of your input is NOT N, it is N^2. For an array of size N, the number of items in the array is N^2, and since you have to deal with all the items, they define your input size. Given that the input size is N^2, we can call it M now, then the runtime complexity is T = O(M), which is linear with respect to the input size.

  2. We express constant time as O(1) as it is equivalent to O(n^0).

    Anything raised to the power 0 is 1.

    So we can only express it as O(1) which is not equivalent to O(2) or O(3) and so on as you demonstrated at 14:56.

  3. I'm sorry but the 151 people who disliked this video need Big O explained to them in crayon. This video is perfect.Thanks a million!

  4. What I am failing to understand is how you got the values for the array for the output of 5 and 10. My reading skills of code isn't too great and I am rusty at the moment. Can you explain it ? thanks

  5. I wish you were my university lecturer – so happy to have found this!! 🙂 It made things make so much more sense!

  6. Wow. Just wow. You made it look so simple. Complexities seemed nightmare before this lecture.
    Can you also please explain Merge Sort's complexity?
    Thanks in advance. 😃😃😃

  7. Sir please can you make a separate video on Formal mathematical definition of Big-O ?
    It would be great. Thanks 🙂

  8. Leonel Hernández

    Hi, have you seen the Berlekamp–Massey algorithm? The time complexity is defined as O(n^2), where n is the input data. Can I asume the same space complexity?

  9. Thank you so much for explaining this. I have a quiz on Big O analysis tomorrow and I was completely lost before watching this video.

  10. Thanks man u made my day! I was stuck at this topic at my college and u made it easy for understanding. Please make more videos on data structures.

  11. It's a shame for me that I have worked with various types of projects but I don't know basic things like this, thank you, you just made my day! 🙂

  12. The mathematical rigorous explanation of Big O Notation would be much appreciated, brother. Thank your for the videos. 😀

  13. I was about to Google Big O Notation when this video appeared in my recommendation and it clears out everything!! Many Thanks!

  14. This is an amazing series man. You really explain soo good. Want to learn everything from you. Lots of love from India 😍😍

  15. Thanks a lot this was great. Would be perfect if there was a 6min version of this, kinda wordy and you lost me many times .

  16. YK, just wanted to say how much I appreciate you for dedicating your valuable time and knowledge to the youtube community of developers. I am starting out fresh as a software developer and CS major this fall. Your videos are excellent learning tools are are helping me to grasp the discipline so thanks man!

  17. If all elements enqueued and all elements dequeued in circular queue then front=0 and rear = size-1 which is the condition of full queue but it is empty .why???

  18. Is this an okay way to implement the find_sum_2d function in python?

    def find_sum(arr):

    total=0
    for i in range(len(arr)):

    for j in range(len(arr[i])):

    total+=arr[i][j]

    return total

    let me know if theres an easier way

  19. You are soooo good i can see why Google hired you. Thanks for the explanation. It is been a while since i needed to remember all of this and it just pops in my mind when you explain it like that.

  20. This video is still understandable in 3x speed, and barely understandable in 4x speed. You really ought to talk faster, or to upload the video at an edited speed. The best speed I found was 2.5x

  21. Thank you for this video, I will be keeping up to date with you data structures class just as some extra help as I just started data structures class and want to learn as much as possible

  22. 14:41 if you're removing all the coefficients then the 1 will also be removed.Instead of that you may write the function as
    0.115 * x to the power 0 so that variable x remains according to the rule(anything to the power zero is 1).

  23. i got a book
    which is very expensive in my country
    some bunch of experts and phds wrote it

    trust me , the book is just bunch of shittiest explanations i have ever seen

    now i feel you taught me this for free
    and its blessing for me

  24. Helpful presentations however the empty boxes you show are kind of annoying. It's better when one can look at the entire code in a glance.

  25. It's clear you know this material, but you spend far too much time tediously explaining the same things over and over. This could easily have been 10 minutes or less.

  26. Thanku very much such a nice explanitaion ..day after tomorrow is my exam and now the concept are getting clear 😀😀😄😃🤟🏻

  27. I wish this series could continue forever. 30 minutes of CS Dojo teaches more efficiently than all the classes at my university combined.

  28. A very good and detailed explanation of Big O notation and time complexity. I'm a college student and I took Data Structure course before but the professor was suck so that I end up did not learn any knowledge about Data Structure. After I watched this video, I really hope that you were my professor at the time that I was learning Data Structure. Excellent video.

  29. CS Dojo, you need to create your own MOOC or something. I swear to god, I would drop cash to buy your course. You explain everything so succinctly and clearly. You are god-tier at explaining this stuff. I WILL GIVE YOU MONEY!!

  30. Great tutorial! Very Helpful! The Instructor is very knowledgeable about the subject and presents the information very clear and concisely, more youtube tutorial presenters should learn to focus on this style presentation format. Thank you for this very helpful video! Sub/d!
    {{ : ]__~~ robogenus }}

Leave a Reply

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