Time complexity analysis: asymptotic notations - big oh, theta ,omega

Поделиться
HTML-код
  • Опубликовано: 19 окт 2024

Комментарии • 205

  • @AnumitKaur0211
    @AnumitKaur0211 9 лет назад +65

    ***** First understand this:
    Given condition is f(n)

    • @gobhai
      @gobhai 8 лет назад +3

      Omg I love you man, thanks a lot for this, cuz this was the only thing stopping me from understanding anything in the video, so thanks again a ton.

    • @gobhai
      @gobhai 8 лет назад +1

      Can you explain the second part ant big omega, u just said that taking n0=0 gives an invalid number but he still took that number , so please solve this confusion.

    • @tayyabikhlaq5354
      @tayyabikhlaq5354 7 лет назад +1

      best one thanks anumit kaur

  • @richardjones7726
    @richardjones7726 Год назад +9

    A big applause to our beloved teachers Harsha and Animesh . Even though Harsha is not with us , his teachings will always be legendary and incomparable . Rest in peace Mr. Harsha Suryanarayana.

  • @emmafoley8987
    @emmafoley8987 4 года назад +9

    Since I was referring to this as a refresher, rather than in introduction, I really appreciated how brief you kept the explanation. Thanks!

  • @abuenavi
    @abuenavi 9 лет назад +4

    This is probably the best explanation of this I have seen anywhere (and from books too). Thank you very much!

  • @mycodeschool
    @mycodeschool  11 лет назад +11

    Hi JoseWanKenobi. Thanks for the comments !!
    When you say above, "For Big O notation, we have c.g(n), that after some point n0 will always be greater or equal than f(n)" , its the same as saying that c.g(n) is an upper bound of function f(n). C.g(n) kind of tells us that f(n) is not gonna pass me over in value ever during its lifetime now that it has crossed n0. So, O(n^2) giving us upper bound means that there is some c such that cn^2 is the upper bound. That's how we say it. :)

  • @mycodeschool
    @mycodeschool  11 лет назад +3

    For Big-oh lets say, we have a function f(n), by finding c and n0, we are trying to find another function in terms of g(n) , like c*g(n) which will always be greater than or equal to f(n). In our example f(n) = 5n^2+2n+1, we choose g(n) = n^2 because, we can create an inequality like (5n^2+2n^2+ n^2) = 8n^2 >= (5n^2 + 2n+1) for n>=1. In most cases, we get rid of the lower order terms by upgrading them to higher order and we get such an inequality. Let me know if its still not clear.

    • @markkithinji2666
      @markkithinji2666 Год назад

      Ive replayed this several times. Im happy to see it here😂😂

  • @DeepSukhwani
    @DeepSukhwani 8 лет назад +136

    The explanations are good, but for a first timer trying to understand asymptotic notations, explaining using text book way of writing sets and all, actually confuses more. I would recommend watching Harvard's CS50's Asymptotic Notations for a rather more pragmatic explanation to this and then come back to this video. It would start making a lot more sense.

    • @TheDood71
      @TheDood71 7 лет назад +29

      Thank you for that. This guy loses me right when he starts up with creating relationships between f(n) and g(n). Why are we not always talking about f(n)...why create this relationship? If f(n) is the function itself, what the heck is g(n) and why establish the relationship when it seems to abstract the problem unnecessarily.

    • @scorpionrao1979
      @scorpionrao1979 6 лет назад +10

      Can you paste the link for CS50 ? When searching, I see a lot of results not sure which one you recommend.

    • @sanjaysuresh97
      @sanjaysuresh97 6 лет назад +3

      Deep Sukhwani Thank you so much for Harvard's CS50's Asymptotic Notations tutorial..

    • @madhurgarg8866
      @madhurgarg8866 6 лет назад +12

      f(n) is the growth function representing the algorithm and g(n) is the general growth function. (n, n^2, log(n) etc.)

    • @adityachopra3759
      @adityachopra3759 5 лет назад

      @@TheDood71 I'm in a similar situation right now. Please help me with this. Why are we making these relationships between f(n) and g(n)???

  • @mycodeschool
    @mycodeschool  11 лет назад +1

    For multiple variables , a function like f(m,n) = 6m + 4n, we need to find C and two more constants m0 and n0, such that for m>=m0 and n >=n0, cg(n) >= f(n). We may even have one constant N such that cg(n)>=f(n) for n>N and m>N , we can pick N as max of n0 and m0. Typically, in such case we will keep both the variables and try g(n) = m+n and deduce c and N = max(m0,n0). Asymptotic notations for multiples variable functions gets a little tricky.

  • @mycodeschool
    @mycodeschool  11 лет назад +1

    Yes, it all comes down to discovering the constants c and n0. Actually, If you are able to deduce the polynomial, then its not that difficult afterwards. It is technically correct to say something like f(n) is O(5n^2+6n). Here g(n) =5n^2+6n. But we typically choose values of g(n) where constants and lower order terms are dropped. A polynomial function in most cases is big-oh of highest order term. Like f(n) = 5n^4 + 6n+1 will be O(n^4), n^4 being the highest order term.

  • @mycodeschool
    @mycodeschool  11 лет назад +1

    For an expression, c and n0 will not be unique, we can have many such combinations. As long as we can find any one so that the inequality is true, we are good. The inequality is different for big-oh and big-omega, so c and n0 have to be different. You can have a look at the constants in the polynomial and try to figure out a C. So, we promoted all lower order terms to n^2 so constants got added and it became 8n^2. Any C greater than 8 would fit the inequality 5n^2 + 2n +1 >= Cn^2 for n>=1

  • @mycodeschool
    @mycodeschool  11 лет назад +1

    is 'a' in your function a constant or variable? if a is a constant, then you can try to deduce c and n0 for g(n) = log2n. If we were having something like f(n) = n + log n, for positive n, log n will always be insignificant compared to n for higher values of n. So you have a choice, either choose g(n) = n + log n or choose g(n) = n, because you know that log n is a lower order term. If a is a variable, we have case of multiple variables, so we kind of have a function f(n,a) and not f(n).

  • @umairalvi7382
    @umairalvi7382 7 лет назад

    mannn you are totally insane the you way taught the concept of big-oh no other video taught me like you do.your concepts in every video are very very clear thank you so much for all your videos of programming and related videos

  • @mycodeschool
    @mycodeschool  11 лет назад +2

    [2] - So, if you are unable to find out simple g(n) , its still ok to find out a complex g(n). and say that f(n) is O(g(n). But because the whole idea is to simplify the time expression, g(n) should be simple and it eventually can be simple in most cases. Hope this helps. Feel free to write again.

    • @khaben6986
      @khaben6986 3 года назад

      sir I just wanted to thank you for your outstanding videos ❤ I'm very grateful to find you during my preparation for exam of data structure and algorithms course and you're helping me a lot ! PLEASE SIR CONTINUE PROVIDING US WITH MORE VIDEOS IN YOUR CHANNEL THEY REALLY HELP 🙏🙏

  • @hiralsingh4099
    @hiralsingh4099 3 года назад +1

    your explainations are so detailed , well versed and interesting ; just like things seemed in coaching days!!! urs is the first video where in i was able to stay focused and also enjoy! Your lectures are much better than that of CN and CB( these are really good but not as interesting as yours)
    pleeeeaaasssee cover all the topics of dsa
    THE STUDENTS NEED YOU!

  • @jyotishmanghatak4191
    @jyotishmanghatak4191 4 года назад

    Ur teaching skills are amazing. Even after watching several videos on time complexity, I couldn't understand it properly but today u made my doubt clear. Thanks a lot

  • @divxxxxxx9647
    @divxxxxxx9647 4 года назад

    I still remember humblefool sometimes and then come here to watch these videos. Also Animesh you're a really really great teacher. My code school is benefitting a lot of students out there. Thank you so much.

  • @Hordaric
    @Hordaric 10 лет назад +33

    Thanks so much! You've changed my life!!!

    • @mycodeschool
      @mycodeschool  10 лет назад +6

      Hordaric You are most welcome :)

    • @yangwang24
      @yangwang24 9 лет назад

      +Hordaric Yeah, also changed my life!!! Thanks to mycodeschool~

    • @roodrraa
      @roodrraa 7 лет назад

      mycodeschool Which writing platform are you using for writing like this? I've noticed that you don't write the total word and it already predicts what you wanna write.

    • @roodrraa
      @roodrraa 7 лет назад

      mycodeschool Which writing platform are you using for writing like this? I've noticed that you don't write the total word and it already predicts what you wanna write.

    • @YTOmkarBhagat
      @YTOmkarBhagat 7 лет назад +3

      They use MS paint and it doesn't autocomplete, they have edited out the parts where they write stuff :)

  • @Mercio2
    @Mercio2 8 лет назад +2

    Thanks! You're an awesome teacher! Greetings from Brazil.

  • @pawan-td6ff
    @pawan-td6ff 6 лет назад +2

    Thank you so much, you have a wonderful way of explaining things. Please keep teaching

  • @RobertTimm
    @RobertTimm 10 лет назад +11

    Thank you! Very well explained. My data structures book could take a lesson from you.

  • @indowestlife
    @indowestlife 8 лет назад +61

    Why didn't you explain how c and n0 are being "assumed" in omega notation?
    And why was the sum of the constants taken for O?

    • @ekhliousful
      @ekhliousful 7 лет назад +1

      I am just started learning programming can you explain more what you mean or lead me to some guides/videos?

    • @kowshikkarmagam8371
      @kowshikkarmagam8371 4 года назад

      yea ..i too have this doubt

  • @OnyxtheFortuitous
    @OnyxtheFortuitous 9 лет назад

    This is my 2nd quarter using your videos. Thank you so much.

  • @mycodeschool
    @mycodeschool  11 лет назад +1

    Hi Bhavya,
    Can you please explain with example what exactly you are trying to find out?

  • @ReginaYe
    @ReginaYe 8 лет назад +3

    best on RUclips I've found on these topics, thank you!

  • @mycodeschool
    @mycodeschool  11 лет назад +5

    Upper bound means you are not going to take more than that. Worst case will be when program will take maximum time. So, upper cap is kind of telling us worst case running time.

    • @itssaket8003
      @itssaket8003 4 года назад

      all of your timecomplexity videos are not playing why?fix this

  • @jphamzz
    @jphamzz 7 лет назад +1

    thank you for explaining this. my professor wasn't able to explain this clearly!

  • @hbreckenridge
    @hbreckenridge 11 лет назад

    For years, I have struggled the concept of time complexity. After watching your video, I know understand the basic of time complexity. Its all based on rate of growth. Well done!!!

  • @billseaman3103
    @billseaman3103 Год назад

    I can finnally figure out what are c and g(n). Clearly language, wonderful video, thank you so much

  • @jlecampana
    @jlecampana 11 лет назад

    Yes, I apologize, I didn't give you proper time to answer, and yes, your previous answers pretty much made things absolutely clear; So, Q: The highest order term in a polynomial is what is referred to as a "Family of functions" ? - ok, to follow up your request, let's say the polynomial is: 1/3 log2n + 5a + 3 .... How would you find c and n0 for that one? - PS. I'm overwhelmed by your kindness, thanks for your explanations, sir!

  • @ayush1137
    @ayush1137 7 лет назад

    Thank you so much for your videos. They are really very helpful in understanding the concept easily. We are expecting a lot such videos from your team.

  • @lucianoinso
    @lucianoinso 9 лет назад +1

    hey, great videos, just one minor correction on the spanish subtitles:
    at time=10m16s it says "Así que estos fueron... el árbol de... notaciones asintóticas", it should say "Asi que estas fueron... las tres notaciones asintóticas"
    The word "three" is translated like "tree", thats all
    Thanks for the videos!

  • @jlecampana
    @jlecampana 11 лет назад +1

    Fantastic, now I know there isn't a difference between the terms, thanks! Now, could you be so kind of explaining to me; What are the rules or procedures to discover c, and n0 for more complex polynomials? (let's stick to big O just for argument's sake)
    Thanks in advance, keep up the good work :)

  • @deprakharjain
    @deprakharjain 4 года назад

    Well explained 👏👏👏
    God bless u man.. From heart❤
    Everything simple, short and to the point👌👌

  • @JoeyGoblins
    @JoeyGoblins 5 лет назад +1

    Better than my professor man, thank you.

  • @jlecampana
    @jlecampana 11 лет назад

    Animesh, What makes us humble novice mathematicians scratch out heads, is when you say/do things like: "because, we can create an inequality like (5n^2+2n^2+ n^2)", Where does this step come from?
    Other than that, the explanation and the video are perfect! (I always come back to it)

  • @khaben6986
    @khaben6986 3 года назад

    I'm in love with this channel 😍😍💖💚👏👏👏

  • @jlecampana
    @jlecampana 11 лет назад

    This is by far, and obviously the best video explanation on Asymptotic notation; I'm glad I found it. Thanks for making it. Anyways, may I ask something? it seems it all comes down to discovering the constants c, n0, right? For a simple polynomial it seems trivial, but can you say the same about more complex equations? How do you proceed in such case? also, Could you please explain to me, what is an "upper bound"?

  • @jlecampana
    @jlecampana 11 лет назад

    in my example, a is a constant :) sorry for not making it clear enough. I will write you in a while If I get in trouble understanding your latest explanation. Thanks again, you saved my life. Fantastic job... Hope to see more and more cool things in this more than awesome channel. :) :)

  • @AbhinavRaman21
    @AbhinavRaman21 10 лет назад +4

    You're the real deal man .... you helped me so much ! Thank You

  • @hemanthsavasere8807
    @hemanthsavasere8807 8 лет назад

    Simple short and sweet, well explained.

  • @educate9796
    @educate9796 8 лет назад +1

    in general, please explain how to calculate n0, c1 and c2. that will be your most kindness.

  • @mycodeschool
    @mycodeschool  11 лет назад +1

    See my answer for your first comment. I have tried to explain. Give me an example of a complex polynomial. It will help me explain further.

  • @AbhijeetSatogiya
    @AbhijeetSatogiya 10 лет назад

    Amazing ! Good job #mycodesschool ! stuck to the topic from the beginning. Gr8 work. Completely Understood.

  • @acoustic_ng8706
    @acoustic_ng8706 11 лет назад

    sir can u plzzzzz make vedio on master theorem sir it is very diffcult to understand
    in algorithms becoz i know that u r the only one who can explain in the simplest way......

  • @whitehood9625
    @whitehood9625 10 лет назад +1

    Thanks for the efort of making these videos and thanks for the subtitles.
    You are realy great. Keep up the good work :)

  • @animeshnayan1
    @animeshnayan1 11 лет назад

    We want to substitute 2n term with 2n^2 and 1 with n^2 to say that
    5n^2 + 2n^2 + n^2 (8n^2) >= 5n^2+ 2n +1 for n >=1. We want to bring everything in n^2 terms so that we could choose constant c.

  • @aryannijhawan8448
    @aryannijhawan8448 3 года назад

    at 7:11 the two graphs should meet for n=n0 since cg(n)

  • @diveshkumar2536
    @diveshkumar2536 7 лет назад +1

    nice tutorial...concepts are explained in an easy way...

  • @GooseBerry390
    @GooseBerry390 7 лет назад +1

    Is big oh notation only for the worst case? I think it's only about the upper bound - it can be used to describe both the average case and the worst case. Likewise for big theta - we can use big theta to describe tight bounds for the worst case too.

  • @Abdullah-mg5zl
    @Abdullah-mg5zl 9 лет назад +3

    Wow, thank you so much for this series! It is FAR more helpful than my textbook/ta/professor (no offense to them though), I think I just need someone to use simpler terns, use lots of examples, and go SLOW when explaining math intense concepts, THANK YOU!

  • @halfaddercircuit
    @halfaddercircuit 7 лет назад

    Nice video. Really helpful. But someone can tell me whether the. video gets glitched in first 2mins?

  • @mycodeschool
    @mycodeschool  11 лет назад +1

    Thanks Herman !!

  • @asdffghize
    @asdffghize 10 лет назад +1

    OMG that was perfect !!! you will change my grate of exam sir , so thank u sooo muchhhhhhh !!!!

  • @kunduruvaishnavi6492
    @kunduruvaishnavi6492 7 лет назад

    You really made my day!thank you so much👏🏻👏🏻

  • @akshayaggarwal2594
    @akshayaggarwal2594 9 лет назад

    At 8:45 when you set c0 = 5 and and c1 = 8, could you have set c1 = 6 or c1 = 7? Great video!

  • @MrWardo2009
    @MrWardo2009 2 года назад

    Thank you for making this video!

  • @jlecampana
    @jlecampana 11 лет назад

    [2] For Big O notation, we have c.g(n), that after some point n0 will always be greater or equal than f(n).... I understand well up until that point, But I just DO NOT understand how out of that concept you say you have an "upper bound". Could you explain this 'difference' further? or succinctly what IS the Upper bound? and how it differentiates from a function that is bigger than f(n) after a constant n0?
    Thanks in advance! I loved your explanation.. sorry my Math is very poor :(

  • @UdayKumar-bw5yq
    @UdayKumar-bw5yq 7 лет назад

    Please explain me how will we determine f(n) and g(n) functions. On what criteria basis.

  • @wolverinelogan9851
    @wolverinelogan9851 10 лет назад

    Thanks for the nice video. I have few questions regarding the calculation of the upper bound for the polynomical. Say for example if we have functions like f(n)=3n+8, f(n) =n^2+1 ,f(n)=n^4+100n^2+50.for these functions how do we calculate the value of c and n0?

    • @mahesh_jamdade
      @mahesh_jamdade Год назад

      We ignore the constants when calculating the time complexity. so, the runtime complexity of those functions are O(n), O(n^2) and O(n^4)

  • @vlad-andreiursu7249
    @vlad-andreiursu7249 10 лет назад

    I have a question. I'm not sure if the following statement is true or false :"Sigma(n) = Small-sigma(n) U theta(n)". Intuitively, I would say that it is true, because the math seems to work and I cannot find an counter-example. Could you please confirm or disapprove my assumption? Thank you.

  • @SiddharthKrishan
    @SiddharthKrishan 9 лет назад +4

    Hi, how you calculated c=8?? Can you explain please??

  • @dikshithavenkat1684
    @dikshithavenkat1684 4 года назад

    what do you mean by input size?
    is it the value of the number you type?
    is it the number of types a particular loop is repeated?

  • @joshbarber89
    @joshbarber89 7 лет назад

    Video would have been perfect if you would've emphasized the use of f(n)

  • @c.danielpremkumar8495
    @c.danielpremkumar8495 7 лет назад

    In the big Oh or Omega notation, what is the meaning of n0 being equal to zero. Under this context, how can you practically have an input equal to zero ? The input value of n should be at least equal to one.

  • @ShortGiant1
    @ShortGiant1 9 лет назад

    THank you so much for the videos.
    However, there is an error in the formal definition of Theta(n) at 8:30.

  • @mycodeschool
    @mycodeschool  11 лет назад

    Thanks Yusuf !!

  • @zonenetplus
    @zonenetplus 10 лет назад

    Please make a video for bucket sort, thank you for great job

  • @subhadeepbabai
    @subhadeepbabai 8 лет назад

    Very Nicely Explained.. Thanks..

  • @ahmadahmadi8398
    @ahmadahmadi8398 11 лет назад

    Thank you so much sir, for uploading such amazing videos... please upload some more lessons on algorithms ... this much is much help full but not enaph sir :) again thanks sir

  • @varshneyabhushan
    @varshneyabhushan 7 лет назад

    Can we say ..theta of g(n) is intersection of omega of g(n) and O(g(n))?
    And omega of g(n) is inverse of O(g(n))?

  • @ManpreetKaurrajput
    @ManpreetKaurrajput 10 лет назад

    hey.... can co and no satisfied with two or more than two values ??? and thnkew for sharing dis amazing video

  • @AbhimanyuAryan
    @AbhimanyuAryan 10 лет назад

    little mistake mycodeschool you said n>=0 this wrong n>= nnot. Suppose we take the sole boundary condition for any recursion T(1) =1 for recursion T(n)

  • @mwerensteijn
    @mwerensteijn 8 лет назад

    Thank you! Excellent explanation!

  • @behrouzsalehipour2384
    @behrouzsalehipour2384 11 лет назад +1

    Very well done.

  • @johnz1611
    @johnz1611 7 лет назад

    how correct is it to say Big O gives us the worst case running time of an algorithm ? Why can't we use Big Omega or Big Theta to give worst case running time of the algorithm ?

  • @typedeph
    @typedeph 9 лет назад

    In your omega graph shouldn't f(n) and g(n) both start at the origin since n0 = 0 for both f(n) and c*g(n)?

  • @anuragreddy391
    @anuragreddy391 10 лет назад

    Could you make it clear in both big oh and omega notation why did we get the n0 values and y did u take 2n^2 in big o and 2n+1 =1 in omega
    Thanks in avance
    Nice video

    • @mycodeschool
      @mycodeschool  10 лет назад +1

      ***** You can choose any value of n0 and any function as long as the inequality is satisfied.

  • @nearriver8174
    @nearriver8174 10 лет назад +1

    thank you so much! I am so glad that I am learning it in high school calculous now :)

  • @davidkim2504
    @davidkim2504 3 года назад

    if f(n) = 5n^2 + 2n + 1, g(n) can also be something like 8n^3 right? Why is it 8n^2? @3:47

  • @RAJESHKUMAR-eb5bh
    @RAJESHKUMAR-eb5bh 9 лет назад

    Sir, plz upload some videos for Space Complexity

  • @agneevsaha1925
    @agneevsaha1925 7 лет назад

    well i now know something in FAAD...xD... thanks dude u helped a lot

  • @chandangupta4104
    @chandangupta4104 6 лет назад

    it is really great explanation

  • @muhammadamir-fq5nl
    @muhammadamir-fq5nl 5 лет назад

    At 7:04, is it not necessary that the f(n) must intersect g(n) at some value in the graph?

  • @ethnictherapy4349
    @ethnictherapy4349 5 лет назад +2

    Big Oh - Upper Bound, meaning Worst Case
    Omega - Lower Bound, meaning Best Case
    Theta - Tight Bound, meaning Average Case

  • @swrhsn6300
    @swrhsn6300 4 года назад

    Can you please suggest the name of the book from where you took this examples

  • @gobhai
    @gobhai 8 лет назад

    Can you explain why you took n0=0 in bio mega notation? +mycodeschool

  • @anishtakkar7
    @anishtakkar7 6 лет назад

    Can somebody explain how we assume C to be 8 for Big Oh and 5 for Omega and also n0 to be 1 for Big O and 0 for Omega ?

  • @erickmartinx
    @erickmartinx 8 лет назад

    finally got it, thanks

  • @ishrathsultana1697
    @ishrathsultana1697 6 лет назад

    You helped me a lot...

  • @atifayaz6554
    @atifayaz6554 8 лет назад

    are these the tight upper and lower bound of the function f(n) if not how to calculate tight bounds?

  • @wangchi562
    @wangchi562 Год назад

    Thanks you so much!!!

  • @Chirayu19
    @Chirayu19 7 лет назад

    Can we choose n square for omega notation in the same example?

  • @ryansingh1742
    @ryansingh1742 6 лет назад

    U r Life savior

  • @baurks
    @baurks 6 лет назад

    I am having tough time understanding Theta. Is it the average time?

  • @djangodude9252
    @djangodude9252 7 лет назад

    If tight bound is better than why don't we use this instead of upper bound?

  • @rifatazim8879
    @rifatazim8879 10 лет назад +1

    Are you assigning random numbers to c1 and n0 in the examples?

    • @mycodeschool
      @mycodeschool  10 лет назад +1

      Rifat Azim We can have any c1 and n0 that can satisfy the inequality.

    • @rifatazim8879
      @rifatazim8879 9 лет назад +1

      I believe they'd both be n^2

    • @rifatazim8879
      @rifatazim8879 9 лет назад +1

      I can't remember whether O(n) is bigger or smaller than O(logn).
      But the rule is whichever one is bigger, then it dominates.
      Sorry did this last year.

    • @fragr33f74
      @fragr33f74 9 лет назад

      +BomBamBum no problem

    • @SreeragNairisawesome
      @SreeragNairisawesome 8 лет назад +1

      +Rifat Azim O(n) > O(logn)

  • @jonbejohns
    @jonbejohns 7 лет назад

    how are C1, C2, and N0 being determined for theta notation?

  • @Inefprag
    @Inefprag 7 лет назад

    I am the 1111th person that liked this video. I feel so privileged

  • @jonnieve2483
    @jonnieve2483 8 лет назад +16

    Our professor sucks. You don't. Thank you :)

  • @maikomandre
    @maikomandre 8 лет назад

    Excelent. Congrats