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

  Рет қаралды 2,058,574

CS Dojo

CS Dojo

6 жыл бұрын

Big O notation and time complexity, explained.
Check out Brilliant.org (brilliant.org/CSDojo/), a website for learning math and computer science concepts through solving problems. First 200 subscribers will get 20% off through the link above.
Special thanks to Brilliant for sponsoring this video.
This was #7 of my data structures & algorithms series. You can find the entire series in a playlist here: goo.gl/wy3CWF
Also, keep in touch on Facebook: / entercsdojo

Пікірлер: 1 500
@ahmadali-zz8om
@ahmadali-zz8om 4 жыл бұрын
After I finish my course I want to send this vid to my professor and tell him to explain it this way to make the student's life easier.
@abeeonaboat1741
@abeeonaboat1741 4 жыл бұрын
Noice
@RizalHilman
@RizalHilman 3 жыл бұрын
Lol
@sansamman4619
@sansamman4619 3 жыл бұрын
savage
@CANIHAZURDREAMSPLS
@CANIHAZURDREAMSPLS 3 жыл бұрын
ikr... why are most eng profs shit...
@nicholasg9804
@nicholasg9804 3 жыл бұрын
Me too homie
@cl0udbear
@cl0udbear 5 жыл бұрын
"I'm gonna use pseudocode" **uses Python** Python: "Am I a joke to you?"
@MrKiraBR
@MrKiraBR 5 жыл бұрын
UAHAUHAUHAUH
@cl0udbear
@cl0udbear 5 жыл бұрын
@@MrKiraBR yareet there pal?
@MagDrag123
@MagDrag123 5 жыл бұрын
Top 10 anime plot twists.
@melvinsoto
@melvinsoto 5 жыл бұрын
My professor does the exact same thing. Assignment: Write the pseudo code for a sorting algorithm and run it. You can’t run pseudo code!!
@cl0udbear
@cl0udbear 5 жыл бұрын
@@melvinsoto Sure you can. Make a state table where the columns are variables/registers/array elements etc and the rows are the state after the line number is executed. Treat the pseudocode as interpreted code, with you standing in for the interpreter, and track the state on the table as you 'run' the code.
@guitarbansi1
@guitarbansi1 3 жыл бұрын
Humble message to all the teachers I ever had: This is how you teach.
@janibhai8215
@janibhai8215 3 жыл бұрын
Dara to mention them @sunil shetty😅😂
@OzozGaming
@OzozGaming 3 жыл бұрын
Yes exactly I hateeee my lecturer
@adamkaraki3389
@adamkaraki3389 3 жыл бұрын
ifkr
@rhalfik
@rhalfik 2 жыл бұрын
Teachers are obsolete.
@RammSkz
@RammSkz 2 жыл бұрын
I'm pretty sure that spending 36 minutes to explain something pretty simple isn't the right way to teach, unless your students are ...
@drewb9162
@drewb9162 4 жыл бұрын
I sat in class for the whole semester struggling to figure this out. Then I see your video and understand it in 30 mins. College is a joke.
@moh11ful
@moh11ful 4 жыл бұрын
That is the problem Teachers who teach us those things Got their computer science degrees from a long ages . They are old , so serous and boring
@muhammedmishal1237
@muhammedmishal1237 3 жыл бұрын
college is an expensive joke
@V-for-Vendetta01
@V-for-Vendetta01 3 жыл бұрын
@@muhammedmishal1237 facts
@GustavoCosta-jr1mh
@GustavoCosta-jr1mh 3 жыл бұрын
You are so right!
@andrewzhang5345
@andrewzhang5345 3 жыл бұрын
In college, you would rigorously define O notation, along with theta and omega. This video isn't rigorously defining it, which is why it's so much easier to understand. In high school, and intro calc class, limits are easy and intuitive to understand, but it's the rigor of the epsilon delta definition that causes so much confusion. I don't think it's fair to say that your professor is a worse teacher when the video isn't necessarily explaining the same content.
@Thunderbuck
@Thunderbuck Жыл бұрын
I'm in my late 50s and starting a DS & A university course, and of course the first term I hit was "big-Oh" and when I saw the academic definitions it nearly triggered a panic attack. I am SO grateful for this engaging lecture and also immensely grateful that the Internet makes such valuable content available.
@Imsupposedtostudy
@Imsupposedtostudy 10 ай бұрын
why are you not fishing or living in a hut
@TheRealTruth65
@TheRealTruth65 8 ай бұрын
Why don"t u study instead of being rude@@Imsupposedtostudy
@AlessandraLopes1
@AlessandraLopes1 7 ай бұрын
We're on the same boat, and this lovely tutorial also saved me from panicking! Keep on going my friend!
@spicytuna08
@spicytuna08 6 жыл бұрын
I went to UC Irvine in Southern Cal. I had a professor (obviously PhD) who graduated from a big Ivy league who explained this. I could not understand. I couldn't F understand from the course book also. Now I understand. You are such a great teacher.
@saveUyghurs
@saveUyghurs 5 жыл бұрын
The ability to teach is truly something only a few ppl who are actually good should be allowed to do. Otherwise, you end up thinking you're the dumb one when really delivery of the material was bad. So many dreams crushed this way
@rushilmehra
@rushilmehra 4 жыл бұрын
Lol pattis
@imtiyazshaikh5331
@imtiyazshaikh5331 4 жыл бұрын
@@saveUyghurs Completely agree. Teaching is not only a highly respected but also a high demanding profession. I think the way teachers are recruited should be totally revolutionized and teachers themselves should prepare and plan the lecture before delivering it.
@joelovalistien9275
@joelovalistien9275 4 жыл бұрын
lmao shindler?
@Sun-yv9fr
@Sun-yv9fr 4 жыл бұрын
Knowledge of effective teaching is what they needed in order to teach effectively rather than just having an Ivy league and Ph.D. background.
@maialso6096
@maialso6096 7 ай бұрын
0:20 sum function 1:30 how much time does it take to run this function ? -> depends on the computer & programming language etc.. some tools to answer the question : Big O notation & Time Complexity 2:40 testing the function in python 4:54 Time Complexity -> Linear time -> constant time -> quadratic time 5:42 Big O notation -> Linear time, O(n) -> constant time, O(1) -> quadratic time , O(n^2) 7:30 how to find big O from an expression -> find the fastest growing term -> take out the coefficient 10:54 convenient features -> gives you a rough idea about how your function scales as input increases -> doesn't depend on your practical environment 12:38 practice_1 17:40 practice_2 -> O(1)+O(1)=O(1) 20:51 practice_3 25:06 practice_4 31:52 practice_5 edit : Free Palestine !!🍉🍉
@fluorescentadolescent2189
@fluorescentadolescent2189 6 ай бұрын
based
@HasnainHamdani
@HasnainHamdani 6 ай бұрын
Free Palestine
@proceduralism376
@proceduralism376 5 ай бұрын
Free Palestine
@jonharvey
@jonharvey 2 жыл бұрын
Thank you for the helpful video! Great examples for a beginner 0:21 Intro w/ example function find_sum 2:40 Testing actual runtime of example function in microseconds 12:37 Another Example: stupid_function O(1) compared with O(n) 17:03 Without Testing runtimes: BigO + TC for stupid_function and find_sum 25:05 Another Example : O(n^2) 34:04 Wrap up
@codewithvenky
@codewithvenky 7 ай бұрын
🎉
@Sarah-uh8wy
@Sarah-uh8wy 5 жыл бұрын
I should be paying my tuition and fees to you lmao Seriously, thanks!
@cruzer6571
@cruzer6571 4 жыл бұрын
Having to pay tuition for going to university/college must suck /🇸🇪
@SauceyRedHN
@SauceyRedHN 3 жыл бұрын
Cruzer ikr 🇳🇴
@Titan_Ruler622
@Titan_Ruler622 6 жыл бұрын
The flow of your explaining is excellent. After getting frustrated from reading this from text books, I came here and now it looks so simple to understand. Really excellent man..☺
@smallcreativecorner5930
@smallcreativecorner5930 4 жыл бұрын
4 years of University couldn't explain what you just did in 40 mins. You truly have a gift!
@mikeallencopeland
@mikeallencopeland 4 жыл бұрын
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!
@gameovertube481
@gameovertube481 Жыл бұрын
Did you graduate now?
@thundersmind
@thundersmind 6 жыл бұрын
Hey Dojo. Keep up with the amazing videos. You're destined for greatness!!
@CSDojo
@CSDojo 6 жыл бұрын
Hey guys, sorry for the delay on this video. I traveled for a week, and I sort of fell out of my routine after that. But I’m back! Anyway, thanks a lot to everyone who messaged me or commented on my videos while I was away. As usual, please let me know if you have any video requests in a comment below :)
@vayabbavayabba9285
@vayabbavayabba9285 6 жыл бұрын
CS Dojo you will start all new languages but you don't continue it And you will start again new language we are suffering
@CSDojo
@CSDojo 6 жыл бұрын
Which languages?
@pavanprabhakar7358
@pavanprabhakar7358 6 жыл бұрын
Bro pls make videos on competitive programming
@YugiohXLight
@YugiohXLight 6 жыл бұрын
CS Dojo what is the complexity of the original sum function? In python i think you could do func = (lambda given_array: sum(given_array))
@chetanhegde1476
@chetanhegde1476 6 жыл бұрын
CS Dojo Please make separate videos on big oh, big theta and big Omega.
@mor11lano93
@mor11lano93 12 күн бұрын
bro, my lecturer just explained it so poorly for 4 hours. And you just made it so understandable in half an hour! good job man thank you
@shrutisharma3146
@shrutisharma3146 3 жыл бұрын
This is by far the best explanation of time complexity and how to calculate it for any function that I have seen on KZbin. Thank you.
@Codebake
@Codebake 4 жыл бұрын
I learnt this concept from a course and I swear no lecturer explained it better than you did. Good work man😎
@dhruvsingh1837
@dhruvsingh1837 3 жыл бұрын
Sir, you are doing a really great job. I am able to understand each and everything in this tutorial. You put so much effort into your tutorials. I cannot thank you enough for this crystal-clear explanation. You even quit your job at google, just to teach and share your knowledge with us and that too for free, mad respect for that. Thanks again sir.
@bootae9246
@bootae9246 3 жыл бұрын
Thank you for this video! You did what my professors couldn’t! You’re really good at explaining in a simple way but getting all the information across anyway! I’ve tried for a week to understand this and your video really helped!
@abvdgr8886
@abvdgr8886 3 жыл бұрын
I remember when I was taking CS Applications I was so confused when watching this video, but now that I am watching it I can’t believe I couldn’t understand it the first time. It’s explained so well!
@mohammedghouse9088
@mohammedghouse9088 6 жыл бұрын
And can you also add O(logn) and O(nlogn)
@scopestacker9787
@scopestacker9787 5 жыл бұрын
No, it has to be a mapping inside O(). O(n -> logn) O(n -> nlogn)
@abilmansurzhuvandykov9981
@abilmansurzhuvandykov9981 5 жыл бұрын
@Youssef Zahir Data Structures and Algorithms in Python [Goodrich, Tamassia & Goldwasser]. Chapter 3
@Jozin2626
@Jozin2626 3 жыл бұрын
I've been struggling with this concept in my data structures & algorithms course, the way you explained it helped 👍
@hasnainmalick8888
@hasnainmalick8888 Жыл бұрын
I tried so many channels and learned something but nobody taught us like you. Your content is too much deep. hats off men
@ZainKhan-ge6kc
@ZainKhan-ge6kc Жыл бұрын
Amazing! my university professors were not able to explain this as well and clearly as you. I'm so happy that I finally understand this concept. Thank you for sharing and taking the time out
@chriscampbell5901
@chriscampbell5901 5 жыл бұрын
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!
@mikehunt3688
@mikehunt3688 3 жыл бұрын
>:( n IS A LETTER NOT A NUMBER HOW DO I MULTIPLY IT
@ifmondayhadaface9490
@ifmondayhadaface9490 3 жыл бұрын
Imagine not being able to understand basic algebra and trying to learn computer science.
@ericcapiz6516
@ericcapiz6516 3 жыл бұрын
i need it explained in crayon.. lolol
@ep1cshay337
@ep1cshay337 3 жыл бұрын
@@ericcapiz6516 same. Pls explain in crayon 🖍 with pictures and colors 🥺
@AstroTibs
@AstroTibs 2 жыл бұрын
A lot of arrogance on display here. No, this video is not "perfect." The instructor could have given examples of a 2D array that was not square. Ultimately, the final example is _either_ O(n²) or O(N) depending on if you're referencing your input size to being either n rows (in a square array) or N total elements. Both descriptions are valid, but you need to clarify. This is an important point that is not discussed. It would have been better to use an example such as: a function that takes each element in a 1D array and multiplies it against each every element, returning the sum of all i×j. That would have resulted in a O(n²) complexity with a 1D input. Everyone would agree on this without ambiguity. It also would have been nice if the video had shown examples of O(n×log[n]).
@insharamin1147
@insharamin1147 3 жыл бұрын
Hey Dojo. It's been a pleasure learning from u. Plz upload the complete explanation for Big O Notation (log, limits etc).
@FORGIVE123N
@FORGIVE123N 4 жыл бұрын
By far the most comprehensive explanation of time complexity and big O notation I've ever met, so simple and clear. Thank you!
@melusimkhize1607
@melusimkhize1607 2 жыл бұрын
One of the best in the world, I found you on my first teaching python using Jupiter notebook. It was unfortunate in my school they were using wing as IDE. Two years later I found you again and I'm fortunate we use the same concept of Data Structure.
@sahilgarg94
@sahilgarg94 Жыл бұрын
Finally, in my current life. I understood this concept. Can't thank you enough dojo.
@retinalhd
@retinalhd 4 жыл бұрын
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.
@hongyichen0611
@hongyichen0611 4 жыл бұрын
I was about to Google Big O Notation when this video appeared in my recommendation and it clears out everything!! Many Thanks!
@ollysalanson9452
@ollysalanson9452 3 жыл бұрын
I started coding two years ago after watching your videos, now I'm back and still getting so much out of your content. Thanks so much for creating this content.
@technogrinder
@technogrinder 5 жыл бұрын
Thanks Bro, I just cleared an interview with the help of this video. Love you from India
@ericgc01
@ericgc01 4 жыл бұрын
The mathematical rigorous explanation of Big O Notation would be much appreciated, brother. Thank your for the videos. :D
@Corvurax1
@Corvurax1 4 ай бұрын
Big(omega)
@kaustubhdesai9262
@kaustubhdesai9262 3 жыл бұрын
I love the way you teach stuff. It is clear, crisp and insightful. Thank you CS Dojo :)
@asadashoori5553
@asadashoori5553 2 жыл бұрын
you simplified the concept in a way that we don't memorize anything but understand them. thank you so much for your clear explanation 🙏
@fiNitEarth
@fiNitEarth 6 жыл бұрын
I really would love to see a explanation on the mathematical details!:) When i wrote programms for maths class I always myself how I could figure out how much time a certain Programm would Take to run and if it's even worth to wait for a result! Thank you for your video
@medgazzeh9884
@medgazzeh9884 6 жыл бұрын
Here is the more accurate mathematical definition of O(something): Let be U(n) and V(n) two sequences then U(n)=O(V(n)) if and only if U(n)=W(n)×V(n) where W(n) is a bounded sequence in other words it exists a natural number 'N' and a real number 'M>0' where for every natural number 'n' with n>N then | w(n) | < M This ( O( ) ) is used to approximate the behavious of a sequence with an other , in other words _ and in the case of time complexity _ the graph of execution time for an algorithms is very similar to the one of the expression inside the parentheses after big O.
@CSDojo
@CSDojo 5 жыл бұрын
Okay! Sorry I just saw this comment - I'll see if I can make it after my trip :)
@tunebrotherdon
@tunebrotherdon 5 жыл бұрын
++++++
@NguyenTrang-je6zg
@NguyenTrang-je6zg 5 жыл бұрын
I would love so too
@eiderdiaz7219
@eiderdiaz7219 5 жыл бұрын
same here
@HarshaVardhan17
@HarshaVardhan17 6 жыл бұрын
Hi CS Dojo really love your content!! Please make more content on python for people coming from other languages like java,c++ gives the differences in syntax, structure in OOP, control statements, inbuilt data structures and important libraries in it. Also missed you for so long !!!😻
@CSDojo
@CSDojo 6 жыл бұрын
Okay sounds good. Thank you for saying that!
@HarshaVardhan17
@HarshaVardhan17 6 жыл бұрын
CS Dojo my pleasure 😇 YK!! Thanks for making videos!!!
@leooel4650
@leooel4650 5 жыл бұрын
Sincerely, what a tremendous talent! Took me 36 minutes to understand everything that I have been struggling to understand for weeks. Thanks YK
@scars707
@scars707 2 жыл бұрын
Fuck that ***pp
@stutigoyal2771
@stutigoyal2771 3 жыл бұрын
This video has literally cleared all my concepts on this topic. Thank you so very much CS Dojo!
@pizzacheeseman2854
@pizzacheeseman2854 2 жыл бұрын
Having just learned to make a sorting algorithm and hash table in C I love when he said “I implemented it in Python” but the pseudo code he wrote is perfectly valid Python already
@Ali-mi9up
@Ali-mi9up 5 жыл бұрын
The box approach is kinda cool, really helps not throw all the stuff at you in one go
@adamkalimi3542
@adamkalimi3542 3 жыл бұрын
Thanks for putting this together. I enjoyed your method of blocking out the equations, and revealing them later. It's very clean. Keep up the good work!
@BlackBlingGirl
@BlackBlingGirl 3 жыл бұрын
Thank you so much! This was so easy and straight forward. No book has ever explained it to me in a way that i got it right away! Thank you and keep up the good work!
@shree2710
@shree2710 6 жыл бұрын
My drug is back! お久しぶりY.Kさん!
@YugiohXLight
@YugiohXLight 6 жыл бұрын
In the first function in 'pseudocode' if you remove each it will be a good python code:)
@CSDojo
@CSDojo 6 жыл бұрын
Haha yes, I noticed it, too :)
@vikrantsingh47
@vikrantsingh47 5 жыл бұрын
Python IS pseudocode
@azizalaliq8
@azizalaliq8 5 жыл бұрын
@@vikrantsingh47 thats why its amazing
@trevandrea8909
@trevandrea8909 Ай бұрын
​@@azizalaliq8 I loveee Python 😍
@andresvodopivec5950
@andresvodopivec5950 4 жыл бұрын
Your explanations are the best I found online regards the topic you cover. Thanks a lot for the effort you put. It is cool that you concentrate on basic concepts and think logically. That is far more important than watching ML videos were they just use libraries. You teach us to be creative and how to be analytical.
@imrych2014
@imrych2014 4 жыл бұрын
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! :)
@cristinalee7276
@cristinalee7276 5 жыл бұрын
You're a fantastic teacher! Thanks for explaining it so clearly.
@jasonfeliz4366
@jasonfeliz4366 5 жыл бұрын
Best tutorial on Big O on this planet. Everything clicked with this video. Far superior than Hacker Rank
@mastle313
@mastle313 4 жыл бұрын
Read multiple books and watched several videos on this subject and i didn't understand anything until I stumbled upon this video. This guy is a legend. If anyone has a hardtime understanding the big O notation, they only need to watch this video!
@FilipMakaroni_xD
@FilipMakaroni_xD 2 жыл бұрын
Great video, I finally understand Big O and how to get it for my programs, the ending was exactly what I was wondering about, what if there's two equally growing highest terms. Someone correct me if I got the wrong expression but since O(2n^2)=O(n^2) I think it's safe to simplify the initialization, addition and return of variables to O(1) when non scientifically determining the big O notation as it will probably never increase the notation more than it would have been anyway
@fairozahmed6888
@fairozahmed6888 6 жыл бұрын
Hey CS Dojo Really love your teaching and content ...I hope you make a lot of videos on Data Structures ..I have watched your other videos ...Awesome Work ..God bless you :)
@naveedakhtar7172
@naveedakhtar7172 6 жыл бұрын
Fairoz Ahmed yes plz data structure n algorithm analysis... more videos on BIG O plz discuss its each n every aspect
@zakirazakira6951
@zakirazakira6951 2 жыл бұрын
Sir your way of teaching is fabulous. Any novice person will become expert from your way of teaching.Hats off to you for this endeavour and fantastic way of teaching. Lots of Thanks to you Sir.
@azamansari889
@azamansari889 5 жыл бұрын
This is by far the best explanation I have come across regarding Big O and time complexity. Thanks buddy
@anikkhan8811
@anikkhan8811 5 жыл бұрын
Hey Sugi! Thanks for this wonderful tutorial. You just nailed it.....Simple, precise and easy to understand. Go ahead, you're doing excellent :) #CSDojo
@jiyunhwang9559
@jiyunhwang9559 5 жыл бұрын
this is a great video! one small correction: for the first find_sum function, i believe total should be total += array[i], rather than i. other than that, great video! kudos to you.
@edmoods
@edmoods 3 жыл бұрын
Finally someone who knows what he's talking about and knows how to explain! Thanks very much! Reminds me of organic chemistry tutor, also an excellent teacher
@brainy3429
@brainy3429 3 жыл бұрын
when I watched this a week ago , I didn't quite understand this.Maybe because that was my very first time to learn Big O and time complexity.But this time,I really understand everything U taught.Thanks sir! and if there were someone out here who didn't understand this right away , don't be discourged.U will understand this when u watch next time.
@NaimaZakaria
@NaimaZakaria 5 жыл бұрын
yes, please make formal definition video. Thank you for posting.
@lemonwithswag2593
@lemonwithswag2593 6 жыл бұрын
Hi, awesome video as always.
@mariale5262
@mariale5262 3 жыл бұрын
You finally made Big O click for me in the first 11 minutes of your video over some of the other 1 hr lectures I tried listening to. THANK YOU SO MUCH
@vamossanjith2906
@vamossanjith2906 5 жыл бұрын
I started watching your videos recently! Its been grt n I have never been through so many programming stuffs in a shorter period any time in my entire life...keep up the grt work (y)
@Yetipfote
@Yetipfote 5 жыл бұрын
"I use pseudocode for demonstration." > shows python 😎
@wenwen1111
@wenwen1111 5 жыл бұрын
HAHAHAH my thoughts exactly, but then that could be his level of pseudo-code.
@youtubeaccount0x073
@youtubeaccount0x073 5 жыл бұрын
Volvox I KNOW ROGHTTTT
@praveenawesome2182
@praveenawesome2182 4 жыл бұрын
Python :am i joke to u ?
@ViAikBreeck
@ViAikBreeck 4 жыл бұрын
"for each" is not Python. :)
@blackheart6897
@blackheart6897 6 жыл бұрын
I am fond of the way of your teaching.
@WhyNotProgram
@WhyNotProgram Жыл бұрын
I’ve been struggling with this concept but you explained it better than most!
@colton-cu5kf
@colton-cu5kf 5 жыл бұрын
Where have you been all my life? You summed up in less that one hour what I have been struggling for weeks to learn. TY!
@RohanVetale
@RohanVetale 4 жыл бұрын
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).
@imtiyazshaikh5331
@imtiyazshaikh5331 4 жыл бұрын
Well, you are stuck in an infinite loop there.
@RK-oe4vt
@RK-oe4vt 4 жыл бұрын
kzbin.info/www/bejne/rKPRq3Sgbs-hpac
@AstroTibs
@AstroTibs 2 жыл бұрын
1 is not the coefficient. 0.115 is.
@kasiviswanath9019
@kasiviswanath9019 5 жыл бұрын
please make video on O(logn) and O(nlogn) Thank u so much for your nice explanation
@awosikaolawoyin5837
@awosikaolawoyin5837 3 жыл бұрын
Please were you able to find a series that explained the O(logn) and O(nlogn) properly?? if yes can you please share as i could not find the series that covers this on YK's channel. Thank You
@vincedinh6285
@vincedinh6285 5 жыл бұрын
I tried to understand this concept on Stack Overflow but had no success. I have a better understanding now. Great explanation! Thank you.
@jonj2547
@jonj2547 Жыл бұрын
Your teaching style is unmatched. Thank you for this video.
@mauarrogs2360
@mauarrogs2360 4 жыл бұрын
THANK YOU FOR THIS VIDEO CANT UNDERSTAND MY PROFESSOR BUT BRO YOU NAILED IT!
@wackmachine
@wackmachine 5 жыл бұрын
The array_2d example solution is incorrect. The input data size is N=Row*Row, since it's generated outside of the function and irrelevant to the function's own complexity. The actual complexity would be O(N) because the function itself is going through each element of the input only once. It's easier to understand if you consider that the same function can be implemented with accepting a one dimensional array (with the same number of elements as the example). Thus the actual function complexity would be O(N).
@adfke8ncx
@adfke8ncx 5 жыл бұрын
You are rigth.
@qiannathancao
@qiannathancao 5 жыл бұрын
If 2d_Array.shape is (n , n), then he: O(n^2) is correct, you are wrong. If 2d_Array.size = n, then you: O(n) are correct, he is wrong.
@philliey
@philliey 5 жыл бұрын
yeah I'm pretty sure he was basing it on the 2d array on the left where it was size n by n. He put the other n by m there to explain rows and columns.
@Cutiepie-ky9oh
@Cutiepie-ky9oh 5 жыл бұрын
Do you happen to know why the formula for stupid_function, is T^2? I understand that its runtime is O(N), but do not know why Time was written as T^2.
@0xD1CE
@0xD1CE 5 жыл бұрын
Actually it's better to say O(n*m), because N is the time it takes to traverse the first array and M is the time it takes to traverse the nested array. But yes theoretically O(N) is also correct.
@MayureshKadu
@MayureshKadu 6 сағат бұрын
It's been a while since I did this - so came here for a refresher. Very helpful and neatly explained. Quite liked the way you illustrated the concept. Keep 'em coming! :)
@malickdiagne
@malickdiagne Жыл бұрын
I have learning it at university at 2013 and i couldn’t understand this s***t. After ten years, i can proudly say i get it. Thanks you guy. You are genius. That’s the best algo complexity’s explanation that ever seen
@liewulong5417
@liewulong5417 6 жыл бұрын
Thanks
@subramanianchenniappan4059
@subramanianchenniappan4059 6 жыл бұрын
Please put formal mathematical definition video for O(n)
@tunebrotherdon
@tunebrotherdon 5 жыл бұрын
+++++
@sophial7317
@sophial7317 4 жыл бұрын
Thanks a lot, YK, you are such a good lecturer, i learned more here than my graduate classes!
@simondavidvgm
@simondavidvgm 2 жыл бұрын
This was a seriously good explanation of big O notation. Excellent work, dude!
@BurningMarmite
@BurningMarmite 5 жыл бұрын
pls make a video about formal mathematical definition of Big O!! I need it very much, so do the rest of us. Very nice video btw, keep up the good work!!!! Love you dawg, see you in heaven ;)
@raveeshmalhotra7347
@raveeshmalhotra7347 3 жыл бұрын
hello brother, in the video, you mentioned that the second function's(the one with for loop calculating sum near 22:35) time complexity as n(O(1)), and T2= O(1)+ n(O(1))+ O(1)...but there is a CONDITION in the FOR loop to check the ENTRY of program control(until i is less than number of items in array), why you didn't consider the TIME TAKEN in evaluating that condition??? can you please explain that??
@bwzffgh7
@bwzffgh7 Жыл бұрын
Because he was trying to keep this as simple as possible. Explaining loop terminating conditions isn't necessary to understand how this time complexity notation works. He also excluded the time difference between passing the array as a value versus a reference. When estimating scalable performance times, that could be a bigger factor than the loop itself.
@frederickrbrock
@frederickrbrock 5 жыл бұрын
I really enjoyed this video. Great Job!! It was a good refresher for me before I started interviewing. I was given some problems to solve as part of an interview and I nailed it.
@tunjiadewoye448
@tunjiadewoye448 Жыл бұрын
Great stuff as usual! Going to make sure to watch all the vids on this Data Structures & Algorithms Series
@dennisramos9270
@dennisramos9270 3 жыл бұрын
Thanks for the great videos! I'm currently using several of them in the classes I teach. The example below is from Blue Pelican Java Lesson 38 by Charles Cook. Your last example with the 2D Array and the example below look like the same idea. However, Cook explains that the Big O value is O(n) because you are essentially adding each element of the 2D array once, that is O(r*c) where r is the number of rows, and c is the number of columns. Could you explain what the difference is? public static int[] addStuff(int x[ ][ ]) { int row, col; int b[] = new int[x.length]; for(row =0; row < x.length; row++) { for(col= 0; col < x[row].length; col++) { b[row] += x[row][col]; } } return b; } Yes, this one is a bit more complicated than the previous ones. Let’s assume we call this method with the following code: int dfg[][] = { {1,2,...}, {0,4,...}, ... }; //Assume this array has r rows and c columns for a int newArray[] = addStuff(dfg); //total of rc = n elements Studying the addStuff method, we note that we go through the outer loop x.length times which is the number of rows, r. For the inner loop we go through x[row].length which is the number of columns, c. Therefore, the total number of times through the code in the inner loop is rc, which in turn is just the number of elements in the entire matrix, n. We can write the Big O value as either O(rc) or O(n).
@ZBlinkZ
@ZBlinkZ Жыл бұрын
From my understanding I think it's because in his example we always have n squared number of elements(number of rows = number of columns), that's why the time complexity is increased. In your example the number of rows and columns are two different variables O(rc) hence O(n). They seem 2 different cases to me that I could easily mix up, if you didn't point this 😀
@dhairya9990
@dhairya9990 6 жыл бұрын
Please make a video talking about "how maths important for programming"
@FsimulatorX
@FsimulatorX 5 жыл бұрын
You need to know addition at the very MINIMUM!
@RajMusicification
@RajMusicification 4 жыл бұрын
Excellent video!. I love the way you narrated the Big O Notation and Time Complexity with good examples. Thanks!
Жыл бұрын
A simple and clear way to explain Big O annotation. Fantastic video, congrats! 👏👏👏
@TheDracnah
@TheDracnah 4 жыл бұрын
Shouldn't the "for each i in given_array:" be 0(n) at 22:28 ?
@oliviervanlier4947
@oliviervanlier4947 3 жыл бұрын
Depends on how you look at it, if you look at the for loop as a compound statement that repeats everything inside n times , you could say it is O(n). Or you could like at the statements inside the for loop and determine their big O notation. Since you repeat those statements n times, you get the big O of the for loop as n times the big O of what’s inside the for loop. So it’s the same thing, the perspective is just a little different. :)
@holymacaroni3319
@holymacaroni3319 3 жыл бұрын
@@oliviervanlier4947 I get what he is saying in the video but isn't it wrong to write n x O(1)? Because mathematically speaking n x O(1) could be written as O(1) + O(1) + O(1) .. n times + O(1) and as we know O(1) + O(1) is still O(1). I just want to make sure I understand, not throwing any hands. :))
@bilalismail5175
@bilalismail5175 4 жыл бұрын
Where the hell was this guy when I was doing my CS Degree !!!!!!!
@isajal07
@isajal07 3 жыл бұрын
Finished my CS degree 3 years ago and Finally, I clearly understood the Big-Oh. Thanks
@xzerium
@xzerium 3 жыл бұрын
*Big O
@uchihasasuke7436
@uchihasasuke7436 3 жыл бұрын
@@xzerium most textbooks call it Big-Oh
@michaelguerrero2632
@michaelguerrero2632 2 жыл бұрын
Dojo please make a video about the formal mathematical definition of big o please. The way you teach is so good, I can't actually find anyone better at teaching data structures and algorithm better than you. Love your vid btw
@vishnuvirat2501
@vishnuvirat2501 6 жыл бұрын
Hi..sir hello. I am a student from India. I am doing Btech 2 nd year now.ECE streem. What should I do now for getting job in product based company.
@CSDojo
@CSDojo 6 жыл бұрын
I would say continue improving your coding skills and work on personal projects! If you can make a project that gets popular, I think that will be really good.
@vishnuvirat2501
@vishnuvirat2501 6 жыл бұрын
CS Dojo will u suggest me how to learn coding. Seriously I don't still to code. And give me ideas about projects. Pls..sir
@sujannag7013
@sujannag7013 6 жыл бұрын
Get some keywords about the domains you like. May be embedded systems, IoT, Machine Learning, etc. Try to search for introductory videos on them. If you find any of them interesting enough, you can then look for groups on LinkedIn, or courses on coursera, udemy, etc. You will also find many blogs and content which you can practise to further hone your skills in that domain. The more your get yourself attached to a field, the more ideas will pop up. Set up github to showcase your work.
@Kannan000
@Kannan000 5 жыл бұрын
search for similar questions and ask your questions on quora
@timofeytsvirko2699
@timofeytsvirko2699 4 жыл бұрын
17:41 - how to find time complexity
@ujjwalnath4240
@ujjwalnath4240 5 жыл бұрын
Amazing video. I was trying to learn Data Structures and this helped a lot. Thanks.
@pauldaviddavies
@pauldaviddavies 4 жыл бұрын
Premiered in 2014 but as sweet in 2020. So relaxed, composed and to the point. I had to subscribe!
@zombieslayamr
@zombieslayamr 5 жыл бұрын
"I'm gonna use pseudocode to explain this..." ... ... ... NAH... *uses Python*
@karthiksk7246
@karthiksk7246 6 жыл бұрын
What if the row and column are not equal will it be O(mn)?? Stupid function 👌😂😂
@ihorbond
@ihorbond 5 жыл бұрын
My exact question too! And I think it would be linear O(n) where n = rows * columns
@boboz5502
@boboz5502 Жыл бұрын
This is a great course! Clear, detailed, and understandable. Much better than all my professors at the University, especially my supervisor...
@nileshsuryavanshi8792
@nileshsuryavanshi8792 4 жыл бұрын
Excellent dude, I wish, I would have a teacher like you.
@user-hy8dn3ux4q
@user-hy8dn3ux4q 29 күн бұрын
Amazing video. I've just started out in Python Programming having had no prior experience and I can confidently say I understand time complexity well enough thanks to this video. Thank you SO MUCH for taking the time to create this content! :)
Big-O Notation - For Coding Interviews
20:38
NeetCode
Рет қаралды 395 М.
I Need Your Help..
00:33
Stokes Twins
Рет қаралды 89 МЛН
Indian sharing by Secret Vlog #shorts
00:13
Secret Vlog
Рет қаралды 44 МЛН
5 Problem Solving Tips for Cracking Coding Interview Questions
19:12
Big O Notation, Time Complexity | DSA
21:17
Telusko
Рет қаралды 49 М.
Introduction to Trees (Data Structures & Algorithms #9)
10:30
Introduction to Recursion (Data Structures & Algorithms #6)
22:37
What Is Big O Notation?
17:45
Reducible
Рет қаралды 309 М.
Data Structures and Algorithms for Beginners
1:18:43
Programming with Mosh
Рет қаралды 1,7 МЛН
I Need Your Help..
00:33
Stokes Twins
Рет қаралды 89 МЛН