A) Drop lower order terms B) Drop the multiplier C) Total running time is sum of fragments. For large input sizes the the run time depends upon the fragment with highest run time D) If there are two cases possible the time complexity depends upon the worst case scenario (the one with largest time complexity)
You should explain the Theta and the Omega general rules as well, it would be awesome, finally I understand how to calculate Time Complexity with your videos. :D
I am in grad school for software engineering and love to program. I've seen a lot of channels, many good ones, but yours is one of the absolute best. I come back to your videos to refresh and learn, pick up stuff that went over my head the first time around.
hi, at the end of this video you mentioned about the next video in the series "calculating time complexity of recursive programs". I cant find it. If you have uploaded more videos in the series please provide links to the complete series.
Hello, in the tutorial we see O(n), O(n^2),O(n^3) time complexities. But when would you associate logarithmic functions to time complexities. When and how would u calculate that time complexity of a particular code is O(logn) or O(nlogn) ?
Hi, Thank you for such informative video. But can you give examples of codes that would at O(lg N), loops would be a certain indication of O(N), or O(N^2) but how about the others? For example, what is the running time of the prime function on your first video? and why? thanks.
this is so helpful, the whole big o thing clicked to me by watching this video. Was still a little confused watching the first few videos in areas but this video made 100% sense to me. especially when you demonstrated just to focus on the areas that have the biggest impact to overall time and the outer and inner loop example was great for me, saying n loop x n loop = n^2 clicked inside my head. thanks again, best big o vid on youtube and ive watched heaps of them. please make some more vids on some recursive examples if you could
Your explanations are some of the best CS videos I have found anywhere, including videos from universities! Your channel has a lot of videos, some idea of which playlists and videos to start with and what to watch next would be great. Great job!
gr8 tutorial guys, can you redirect me to any other of your videos where the running time of actual program is calculated, It will be great if there are examples and questions , thankx
Please start making videos. I can't imagine how easier and clear it would be for CS students if you cover all these DSA and programming topics. Because these are the topics everyone has a hard time with. But sadly, uppar wala doesn't want this to happen; god took your mate and you are alone in the project. GOSH. Just imagine this channel had all playlists for DSA subjects. The world would be much better with everyone being a good programmer discarding these existing shitty so-called professors.
"In next of couple of lessons we will see different time complexity functions and their comparison and we will also see how to analyse the time complexity of recursive functions". Been a decade and I guess "the next couple of lessons" are slow at uploading on UA-cam!
Hi... Thank fr the awesome explanation.. One small doubt is.. In ur previous video the time taken to exit a for loop is n+1..one extra loop fr the false condition.. But here u go with n times on for loop??
now doesnt need to take the class from that bullshit teachers who even dnt have knowledge about there subject.. because u are here .. thanks u very much
the outer loop runs n times. each time we run the outer loop, we run the inner loop since j is always set to 0 and it increments by 1 until it reaches logn (so it runs logn times) so we do the whole thing is (times you run outer loop) * (times you run inner loop) = n * logn
Thank you for these videos! The book I was studying started talking about O() time, which I generally understood, but then it started in on T() time and using them in equations together also and I couldn't work out what made the two different and how they fit together. These videos gave me a clear perspective with which to finish my chapter.
At 4:38, O(n+1) might come as loop would even check/compare i=n and then return false.... but it would use time in comparing! If n tends to infinity than we can neglect constant and keep it as O(n)
Hello sir.. u did lots of efforts to make us understand the above Complexity topic, but to make a perfectionist over this topic would you please upload some more videos over this topic by which we will get over all concept of complexity like log(n),log k(n),log b(n) etc related to this ..thank you so much anyways :-)
Finally! A video where I got the understanding of time complexity. Thankyou so much for this incredible explanation! Subscribed to your channel after watching this 1st video itself! Thankyou!!
So appropriate!!! It is so hard to find a correct explanation. There is no certainty of material available on the internet. This series seems correct so far! VVVVVEEErrrryyyy Good!!!!
really sir all these classes were crystal clear 2 me, although i have joined a separate course for this i barely understood this topic, thank u very much ..but what about the further topics ..... please post them ASAP... looking forward to them
Hi Sir. First Thanks for making things crystal clear. I have a question, at last, we discussed the if and else and we took the worst case which is true for O. Instead of going to big O can we have solved that using theta that gives the tight bound ??
But As you said that big-oh represents the set,then how can they be added?there should be a union between them.And then in set terms,there is nothing like lower order terms,so they can't be ignored.
What about time complexity of mathematical functions. In particular, matrix multiplication. Say, vP where v is a (1 x n ) vector and P is an (n x n) permutation matrix.
He is one in a million, best among many, most trusted , I almost gave up on trading then I met him through a friend, Austin is the most trusted trading expert who helped the life of my family and I ,.
Are you a university professor? If not, you should seriously consider it. You've managed to teach how to calculate time complexity better than any of my professors.
well he's harsha s. a top coder in the country of the time. yes the country. we'll always remember him. RIP Harsha Suryanarayana. you may have gone but your work will live on. long live humblefool
Gehad Gaber You are correct about the number of comparisons. However, even if it was only n-1 comparisons, or even 2n comparisons, they both would be classified as O(n) complexity.
Sir please clarify that when we are computing the running time of the simple for loop,do we not need to consider the time taken for every comparison and increment by for loop,for n+1 times,including the one time the condition becomes false and loop is exited,as was told in the previous video of model machine??here we are only considering the running time of the simple statements,why so?
6 years later and this is still the most clear and concise explanation I've seen
9*
10*
11
11 years later
A) Drop lower order terms
B) Drop the multiplier
C) Total running time is sum of fragments. For large input sizes the the run time depends upon the fragment with highest run time
D) If there are two cases possible the time complexity depends upon the worst case scenario (the one with largest time complexity)
In a nutshell.
this is gold
Thansk Wayne :)
+BomBamBum O(n^2) the both
+mycodeschool this is god
Old is gold
and still gold
Thank you so much!!! I barely understood the topic and your video made it all clear for me! If I could, I would have given you a thousand likes! :)
Thanks Uri Yakir
1 dislike lets find that bastard :(
+BomBamBum for the first question, the runtime should be log n. for the second question, the runtime should be n log n
+Pond. Filler- may I ask how did you get log(n) for the first question?
so what's up with life now champ, what did you do ?
You should explain the Theta and the Omega general rules as well, it would be awesome, finally I understand how to calculate Time Complexity with your videos. :D
Sure Tudor, we will try to get more. :)
I am in grad school for software engineering and love to program. I've seen a lot of channels, many good ones, but yours is one of the absolute best. I come back to your videos to refresh and learn, pick up stuff that went over my head the first time around.
Awesome! Where are the follow-up videos?
ua-cam.com/video/ncpTxqK35PI/v-deo.html
Sure ! stay tuned :)
Most Clear and Concise Explanation.
hi, at the end of this video you mentioned about the next video in the series "calculating time complexity of recursive programs". I cant find it. If you have uploaded more videos in the series please provide links to the complete series.
Sad to hear about your friend's story Animesh, Stay Strong!
loop runs n+1 times and statement inside it runs n times , right?
Hello, in the tutorial we see O(n), O(n^2),O(n^3) time complexities. But when would you associate logarithmic functions to time complexities. When and how would u calculate that time complexity of a particular code is O(logn) or O(nlogn) ?
Hi, Thank you for such informative video. But can you give examples of codes that would at O(lg N), loops would be a certain indication of O(N), or O(N^2) but how about the others? For example, what is the running time of the prime function on your first video? and why? thanks.
this is so helpful, the whole big o thing clicked to me by watching this video. Was still a little confused watching the first few videos in areas but this video made 100% sense to me.
especially when you demonstrated just to focus on the areas that have the biggest impact to overall time and the outer and inner loop example was great for me, saying n loop x n loop = n^2 clicked inside my head.
thanks again, best big o vid on youtube and ive watched heaps of them.
please make some more vids on some recursive examples if you could
Your explanations are some of the best CS videos I have found anywhere, including videos from universities! Your channel has a lot of videos, some idea of which playlists and videos to start with and what to watch next would be great. Great job!
Best explanation of time complexity analysis. Thanks a lot for the video.
gr8 tutorial guys, can you redirect me to any other of your videos where the running time of actual program is calculated, It will be great if there are examples and questions , thankx
seeing comments from 4, 5, 6 , 7 years ago is so eerie it gives me chills...
This tutorial video was so well explained. Suddenly entire concept is looking so simple!
nice tutorial but where are next comming tutorials on timecomplexity ?
+mycodeschool What about the complexity O(logn) and O(nlogn) wrt the code? Can someone please tell me?
Please start making videos. I can't imagine how easier and clear it would be for CS students if you cover all these DSA and programming topics. Because these are the topics everyone has a hard time with. But sadly, uppar wala doesn't want this to happen; god took your mate and you are alone in the project. GOSH. Just imagine this channel had all playlists for DSA subjects. The world would be much better with everyone being a good programmer discarding these existing shitty so-called professors.
Excellent lecture on time complexity, thanks for posting!
you are my savior!!! I couldn't have passed any of my classes without you.
please tell me you continued this series somewhere ???
hes no more
"In next of couple of lessons we will see different time complexity functions and their comparison and we will also see how to analyse the time complexity of recursive functions". Been a decade and I guess "the next couple of lessons" are slow at uploading on UA-cam!
Bhai!!!! Yaar really good explanation for the first time i get clear about time complexity. Such a simple and good explanation!!
Take a bow. Amazing explanation. I find myself lucky that I have found this video in my search results.
sir you are my god..awesome teaching..plzz do more on algorithms plzz sir so that we can get help in our gate
2:49
I think here time complexity is O(log n).
Correct me if I am wrong.
Great Work Appreciated.
for(i=n;i>0;i--){
for(j=0;j
Wow what a great start on algorithams :) , you have explained very well and made a great foundations. Thank you so much!!!!
please make video on implementation of calculating time in c++
for 16n +logn its O(n).Then what is the time complexity of 16n +n logn ..?
Where are the other videos on recursion time complexity ?
he died
how did u know? he is not died .. a frnd of his is died in accident..check fb post of codeschool
The creator died in a car accident.
I had been looking all the wrong places, awesome
Hi... Thank fr the awesome explanation.. One small doubt is.. In ur previous video the time taken to exit a for loop is n+1..one extra loop fr the false condition.. But here u go with n times on for loop??
yes,, i agree with you..when we use n, or n+1 ?
It is a really good teaching video, well explained, thanks you so much!
Thanks for your kind words Anthony :)
actually the for loop will be executed n+1 times because the loop will check the false case also , so the equation will change please correct it
now doesnt need to take the class from that bullshit teachers who even dnt have knowledge about there subject.. because u are here .. thanks u very much
i wanna give u big thanks since, u present the time complexity in a easiest way ever seen. keep it up
What if we have two nested loops and we have the equation like O(n^2) + O(n^2) , both have the same order, what will be the time complexity ?
my god why did i find this guy so late. this man is amazing
for(i=0;i
+Aakash Varma it would be 0(n^2)
+Aakash Varma nlogn
Shivam Kashyap How?
+Rambo Rambo
it is nlogn. The nested loop only increments j upto log(n) then the loop exits, so the combined run time is n*log(n) = nlogn
the outer loop runs n times.
each time we run the outer loop, we run the inner loop since j is always set to 0 and it increments by 1 until it reaches logn (so it runs logn times)
so we do the whole thing is (times you run outer loop) * (times you run inner loop) = n * logn
Thank you for these videos! The book I was studying started talking about O() time, which I generally understood, but then it started in on T() time and using them in equations together also and I couldn't work out what made the two different and how they fit together. These videos gave me a clear perspective with which to finish my chapter.
What if there is no else part in the time complexity problem? What will be the worst-case scenario then?
At 4:38, O(n+1) might come as loop would even check/compare i=n and then return false.... but it would use time in comparing! If n tends to infinity than we can neglect constant and keep it as O(n)
Hello sir.. u did lots of efforts to make us understand the above Complexity topic, but to make a perfectionist over this topic would you please upload some more videos over this topic by which we will get over all concept of complexity like log(n),log k(n),log b(n) etc related to this ..thank you so much anyways :-)
Finally! A video where I got the understanding of time complexity. Thankyou so much for this incredible explanation! Subscribed to your channel after watching this 1st video itself! Thankyou!!
So on the last part, supposing the condition was "if n
Thanks a lot Stavros. We will try to get more in this series.
What would be θ of the last example. Is it
c'g( n^2 )
Thanks Madhu.
So appropriate!!!
It is so hard to find a correct explanation. There is no certainty of material available on the internet.
This series seems correct so far!
VVVVVEEErrrryyyy Good!!!!
really sir all these classes were crystal clear 2 me, although i have joined a separate course for this i barely understood this topic, thank u very much ..but what about the further topics ..... please post them ASAP... looking forward to them
Hi Sir. First Thanks for making things crystal clear. I have a question, at last, we discussed the if and else and we took the worst case which is true for O. Instead of going to big O can we have solved that using theta that gives the tight bound ??
On the last algorithm if the case is different the complexity is going to be O(n)..
So can we say that the whole algorithm has Ω(n) complexity?
But As you said that big-oh represents the set,then how can they be added?there should be a union between them.And then in set terms,there is nothing like lower order terms,so they can't be ignored.
The only and only explanation that helped me understand this analysis. Really thankful for the effort you put into making these videos.
You guys aer really awesome. Please continue to make. Love 😍
Very Clear Explanation... Thanku so Much....
you dont know but actually you are doing a great service to the student community...lucky to come across your videos...
Now im dare bung class. mycodeschool is here to tech me.
Very good, informative and excellent work. Keep going
bestest ever
What is the complexity If the function I derived is O(m^2) + O(n^3) ?
koi plz bta skta ha k ak statement may jo big power hoti ha wou leani hotI ha koa???
plz tello quickly
my quiz is tomorrow
I think first loop execute n+1 time and the statement of this loop execute n times........... If i am right please correction it
loop 0 to n-1.then it goes n,and exits because conditions dont match.total n times
What about time complexity of mathematical functions. In particular, matrix multiplication. Say, vP where v is a (1 x n ) vector and P is an (n x n) permutation matrix.
Great explaination after 9 years it is also clear to understood
U r a grt teaher!!!
he was a great teacher , he's no more now! may god bless his soul
Thats how its done for any practical purposes.
He is one in a million, best among many, most trusted , I almost gave up on trading then I met him through a friend, Austin is the most trusted trading expert who helped the life of my family and I ,.
-+/1/5/3/0/4/2/8/5/8/70/W/h/a/t/s/A/p/p/< With> /
A/U/s/t/In/.
Thanks a lot Bro .... Really Appreciate your Efforts and very well explained.
best video ever on time complexity
I suddenly wonder that if s
Same things have taught in geeksforgeeks video...
Thank you so much for such amazing content!
Wow your explanation is very clear. our lecture spend hours to explain this
why dont you explain that for looping execute n+1 times? not n times
You're among those few who provide playlist link in the description !
in case someones wondering why he isnt uploading anymore...welp hes dead :(
Thanks a lot Josey !
Thank you this cleared up a lot!
This was exactly what I needed to hear. This should be taught prior to backward substitution.
This was very helpful. Thank you!
thanks for good video series on time complexity, you said next video, means it will coming into this playlist?
Pjysics Maths Ds everything is based on approximation
It was very helpful thanks a lot to u....
Are you a university professor? If not, you should seriously consider it. You've managed to teach how to calculate time complexity better than any of my professors.
well he's harsha s. a top coder in the country of the time. yes the country. we'll always remember him. RIP Harsha Suryanarayana. you may have gone but your work will live on. long live humblefool
@@trueresources3847 Thanks for sharing. I just read the story, that's really sad.
please provide content in python language
sir in the pseudo code the for loop always starts with i=1
and since it's (for i=1 , i
Gehad Gaber in this case yes the overall loop will be executed 1+n+n = 2n+1 times.i,e i=1 this will be executed 1 time, i
Gehad Gaber You are correct about the number of comparisons. However, even if it was only n-1 comparisons, or even 2n comparisons, they both would be classified as O(n) complexity.
I know this is old but you’re the best!
i wish you were my roomate
crystal clear !! thanks !! but no follow up videos :/
Sir please clarify that when we are computing the running time of the simple for loop,do we not need to consider the time taken for every comparison and increment by for loop,for n+1 times,including the one time the condition becomes false and loop is exited,as was told in the previous video of model machine??here we are only considering the running time of the simple statements,why so?
Comparison is also a simple statement . So all simple statements add up giving some const times n. So the overall time complexity is O(n)
We need a continuation of the series, please
Thanks. Very very helpful.