Я готов это пересматривать, этот курс, по много раз(новый учебный год , новый пересмотр), даже когда ты говоришь на инглише и при этом я не понимаю, что ты говоришь)) Спасибо Огромное За Видео!
Content of this lecture: 1. What is algorithm? 2. Definition of Time and RAM complexity 3. Big O notion, Big Omega notion, Big Theta notion 4. Bunch of time complexity samples (Linear, Root, Log, Recursive Functions) 5. Insertion Sort (Intro, Pseudo code, Time complexity) 6. Merge Sort (Intro, Pseudo code, Time complexity) 7. Time complexity analysis of general divide & conquer algorithm (Recursive & Merge)
I have to give it to you... I think the video started slow paced and kinda confusing and hard to follow but i gotta give it to you as time passes it gets really interesting.. way to go.. keep'em coming good work!!
At 12:24, when he asked if anyone knows what RAM stands for, I couldn’t resist the urge to proudly say, ‘Random Access Memory!’ It was always a common question on my exams when I was a kid. Haha, good times!
@pavel What will be time complexity of this solution: class Solution{ private: int count = 0; public: int pathSum(TreeNode* root, int targetSum) { recurse(root, targetSum, false); return count; } void recurse(TreeNode* root, int sum, bool must) { if (root == nullptr) return; if (root->val == sum) { count++; } if (!must) { recurse(root->left, sum, false); recurse(root->right, sum, false); } recurse(root->left, sum - root->val, true); recurse(root->right, sum - root->val, true); } };
No, Ω(f(n)) is the asymptotical lower bound for the function, same as O(f(n)) is an upper bound. We use both these bounds to analyse the worst case time complexity. We use O when we want to prove that the algorithm is fast, and use Ω to prove that the algorithm is slow, but both for the worst case
@@pavelmavrin I read on geeksforgeeks that big-omega represents lower bound & best case, and big-O represents upper bound & worst case, and big-theta represents average case. But I guess geeksforgeeks docs are being written by public. I'll take ur word. Thanks :)
hey , can i start my algo journey from here , with having some knowledge of syntax in cpp or you suggest me some other way. Also, should i follow clrs along with this course?
@@pavelmavrin I get it now. It depends on the scale function of n per level, so height remains the same as the binary tree. It needed few more words though. You have demonstrated things in detail. So here, drawing the relationship of the base with the branches and the scale function, might have made it more easy to follow. I was lost at this point. The rest was a breeze. Thank you for the effort. :clap:
Hi Pavel, About "worst case lower bound" Ω(op) vs "worst case upper bound" O(op)… In Big-O lecture, U've used the example of f(n) = 5 + 2n to define O(op) and Ω(op) I'm unable to clearly understand what exactly Ω(op) represents! Is there any popular algo with different upper and lower bounds in worst case? If yes, cud u pls write them. I might understand better Thankyou! :)
Let's say the worst case time complexity of your algorithm is T(n) = 5 + 2n. You may say that T(n) = O(n²), that's absolutely correct statement, also you can say that T(n) = O(n log n), that's also correct. From the other side, you may say that T(n) = Ω(log n) or T(n) = Ω(sqrt(n)), and so on. If you have the same function in O and Ω, it means you actually found the tight bound of your function, there is even a special letter for this case Θ, so T=Θ(n) just means that T=O(n) and T=Ω(n). So if your O and Ω bounds are different, it just means you don't know the actual complexity of your algorithm, but you know it is between these two functions. All algorithms we discuss in this course are well studied, so it does not happen. On the other hand, in practice you usually care only about upper bound. For example, if you prove that your time complexity is O(n log n), it means your program will make at most c log n operations. If it is good enough for you, it's fine. Even if real time complexity is Θ(n loglog n). You don'n need to know the real time complexity, you only need to know, that it is fast enough. Hope it helps)
@@pavelmavrin I think I totally understood now. Thanks for ur "patient writeup" :) I got confused because while computing worst case time complexity for "stage 1 OPs find() & union()" of Disjoint Sets, u wrote on board T(n) = Ω(n²), but not T(n) = O(n²) Now I understand from ur explanation that upper and lower bounds would be usually the same for popular DSes and ALGOs, and even if they are different we're mainly interested in upper bound, and even if we wanna compute lower bound, we can do the following : First compute the upper bound. To start with, assume lower bound is same as upper bound, and check via "induction" if we get valid values for 'n' and 'c', and also check via "common sense approach" if such lower bound makes sense for the problem (whatever problem is being analyzed) Thankyou! :)
Subscribing to you is the least of the support I can extend for this amazing series
Thanks for the tutorials in English, pashka! orz
agree , we need in english
orz means what ?
@@larknoone565 a posture emoticon representing a bowing
A friend recommended me this video, and I've been blessed.
Я готов это пересматривать, этот курс, по много раз(новый учебный год , новый пересмотр), даже когда ты говоришь на инглише и при этом я не понимаю, что ты говоришь))
Спасибо Огромное За Видео!
I am here to learn cause your student suggested to come here. Thank you for this !
THIS IS THE BEST COURSE EVER .THANKS SENPAI.
I am here from KGP queries page...this lectures are absolute gold...Thank you sir.
thank you for such a precious course for the student who can't able to study at big university. Big Thanks From The INDIA..............
bro should i invest my time on this course? is it worth it?
I enjoyed the lecture and the sounds you made. Keep up the good work and also design challenging and interesting assignments!
Most awaited 🔥💜
Content of this lecture:
1. What is algorithm?
2. Definition of Time and RAM complexity
3. Big O notion, Big Omega notion, Big Theta notion
4. Bunch of time complexity samples (Linear, Root, Log, Recursive Functions)
5. Insertion Sort (Intro, Pseudo code, Time complexity)
6. Merge Sort (Intro, Pseudo code, Time complexity)
7. Time complexity analysis of general divide & conquer algorithm (Recursive & Merge)
it will be nice if you add timelines into your description )
@@theresweet984 I will try :)
I have to give it to you... I think the video started slow paced and kinda confusing and hard to follow but i gotta give it to you as time passes it gets really interesting.. way to go.. keep'em coming good work!!
Thank you Maestro!
- future generations
Thank you, please complete this series. I promise I'll finish them and learn something. Thanks
Hey...how are u? Have you completed it and how's this course.. should I follow it?
@@GautamKumar-lh7ulyes, you should!!!
At 12:24, when he asked if anyone knows what RAM stands for, I couldn’t resist the urge to proudly say, ‘Random Access Memory!’
It was always a common question on my exams when I was a kid. Haha, good times!
Thank you sir, could not be more indebted!
Much awaited course ....❤️
But , be continuous while uploading lectures ✨
you can watch friday at 8:30 IST live
Ohh mai... Finally I can take more knowledge easily😁
Woah that guitar intro is soo cool I just watch the video again and again to see that intro 🙃🙃
great lecture man, You just looks like Edward Snowden brother
Thanks for the lectures and ur time 😀 ,
Love from India
You are doing God's Work here, Thank You
Thank you for English sirr keep uploading
really good learning experience
Examples end at 53:44
Sorting algorithms start at 53:45
why did you write "if b = m" in merge sort 1:11:22 as the types of b and m doesn't match each other?
1:17:02
You are next to god sir
I'm ready for this
That cat made me subscribe. :)
That's her purpose :)
@@pavelmavrin that's what she said
Playing guitar well, ♥️. thanks for this lectures
Thanks you my friend
54:00 sorting algorithms
so excited to get my rank to rise by 2k points in the next 2 years
Thanks alot. Was waiting eagerly 💜
Some cases are missing: if f(n)= O(n^logba* (logn)^c), c > 0, then T(n)= f(n)*logn
Man you are the Best!!!
Which is the other series for Cp can someone provide the link?
you are the best
noice sir..................keep it up
Please do continue to post the videos in English...
@pavel
What will be time complexity of this solution:
class Solution{
private: int count = 0;
public:
int pathSum(TreeNode* root, int targetSum)
{
recurse(root, targetSum, false);
return count;
}
void recurse(TreeNode* root, int sum, bool must)
{
if (root == nullptr) return;
if (root->val == sum) { count++; }
if (!must)
{
recurse(root->left, sum, false);
recurse(root->right, sum, false);
}
recurse(root->left, sum - root->val, true);
recurse(root->right, sum - root->val, true);
}
};
Surely it is required to be in pow(4, something)
But what would be value of that something...
Bcoz I'm unable to get depth of recursive tree
1:03:00 -- Is O(best case) same as omega Ω(f(n)) ?
No, Ω(f(n)) is the asymptotical lower bound for the function, same as O(f(n)) is an upper bound. We use both these bounds to analyse the worst case time complexity. We use O when we want to prove that the algorithm is fast, and use Ω to prove that the algorithm is slow, but both for the worst case
@@pavelmavrin I read on geeksforgeeks that big-omega represents lower bound & best case, and big-O represents upper bound & worst case, and big-theta represents average case. But I guess geeksforgeeks docs are being written by public. I'll take ur word. Thanks :)
pashka orz
awesome :)
hey ,
can i start my algo journey from here , with having some knowledge of syntax in cpp or you suggest me some other way.
Also, should i follow clrs along with this course?
Hi Pavel,
On the task I can't get what is the // symbol meaning:
for i in range (n ) :
j = i
while j > 0:
j = j // 2
It surely means integral division, if pseudo code was in context of python language
Good
sir Could you plz explain time complecity of recursion f(m,n) = f(m-1,n)+f(m,n-1)+O(1) of this type
Is there a textbook required for this course?
m-ary tree height is log_m(n), so Ternary tree of n nodes should have a log_3 (n) height.
that's correct, so what is your question? in lecture we had ternary tree, but its height is log_2(n), so the number of nodes is not n.
@@pavelmavrin why the height of the ternary tree is log_2(n)? What is the reasoning behind the base being 2 in the video? Not 3.
because the recursion in the example that we discuss goes from n to n/2
@@pavelmavrin I get it now. It depends on the scale function of n per level, so height remains the same as the binary tree. It needed few more words though. You have demonstrated things in detail. So here, drawing the relationship of the base with the branches and the scale function, might have made it more easy to follow. I was lost at this point. The rest was a breeze. Thank you for the effort. :clap:
It'll be very very very helpful for Students like us if you sire add the english subtitles on your past videos (they're in Russian language)
join us online on Friday
🔥🔥🔥
bhai do saal tak to clg hi khatam ho jayegi...........
@@sawanpatel9421 bachegi bhai college 7th sem tak rev hota rahega
@@sanskarbhargava1842 7th tak to apan hi cm hoge to iske lecture kyu dekhge........
@@sawanpatel9421 haan waise yeh bhi sahi hai 🔥🔥🔥
@@sanskarbhargava1842 shi lecture hai kya ... follow karna chahiye kya?
Where can I get solutions to the home task problems ?
1:02:34 the worst case should be n! , No? 🤔
@@thinker8190 why?
Thanks for this amazing content. Please do beginner videos also!
Can't thank enough
ohhhhhh my GOOD
Great :D
thank you so much sir , please please please add subtitle
Nice
Day 1 Notes:
Big O notation,omega notation and theta notation
Is this course in c++
Python
@Satish_deepvoice thanks
Hi Pavel,
About "worst case lower bound" Ω(op) vs "worst case upper bound" O(op)…
In Big-O lecture, U've used the example of f(n) = 5 + 2n to define O(op) and Ω(op)
I'm unable to clearly understand what exactly Ω(op) represents!
Is there any popular algo with different upper and lower bounds in worst case?
If yes, cud u pls write them. I might understand better
Thankyou! :)
Let's say the worst case time complexity of your algorithm is T(n) = 5 + 2n.
You may say that T(n) = O(n²), that's absolutely correct statement, also you can say that T(n) = O(n log n), that's also correct. From the other side, you may say that T(n) = Ω(log n) or T(n) = Ω(sqrt(n)), and so on.
If you have the same function in O and Ω, it means you actually found the tight bound of your function, there is even a special letter for this case Θ, so T=Θ(n) just means that T=O(n) and T=Ω(n).
So if your O and Ω bounds are different, it just means you don't know the actual complexity of your algorithm, but you know it is between these two functions.
All algorithms we discuss in this course are well studied, so it does not happen.
On the other hand, in practice you usually care only about upper bound. For example, if you prove that your time complexity is O(n log n), it means your program will make at most c log n operations. If it is good enough for you, it's fine. Even if real time complexity is Θ(n loglog n). You don'n need to know the real time complexity, you only need to know, that it is fast enough.
Hope it helps)
@@pavelmavrin I think I totally understood now. Thanks for ur "patient writeup" :)
I got confused because while computing worst case time complexity for "stage 1 OPs find() & union()" of Disjoint Sets, u wrote on board T(n) = Ω(n²), but not T(n) = O(n²)
Now I understand from ur explanation that upper and lower bounds would be usually the same for popular DSes and ALGOs, and even if they are different we're mainly interested in upper bound, and even if we wanna compute lower bound, we can do the following :
First compute the upper bound. To start with, assume lower bound is same as upper bound, and check via "induction" if we get valid values for 'n' and 'c', and also check via "common sense approach" if such lower bound makes sense for the problem (whatever problem is being analyzed)
Thankyou! :)
Can someone tell me which course he was talking about for competitive programming at codeforces at the beginning?
codeforces.com/edu/courses
@@pavelmavrin thanks sir
thank you very much sir!!
Интро топ
well, again twenty five...
so sad that ur content is in russian 😢!