Time Complexity of Code Using Summations
Вставка
- Опубліковано 4 лип 2015
- Compute the following code fragments time complexity using summations.
To see how to convert other such programs checkout:
• Compute The Time Compl...
and
• Prove The Time Complex...
and
• Big-Oh Of The Code Seg...
Please subscribe !
►Website: everythingcomputerscience.com/
►Support this channel on Patreon: / randerson112358
►Support this channel for FREE by doing your Amazon shopping through this link (bookmark it!): www.amazon.com/?tag=randerson1...
Finally someone that actually does something else than "Well you see here, it is in O(n^2)."
Words cannot describe how much I love you for making this video. Your tips and notes and little explanations, the live "troubleshooting" throughout the whole video, it helped me here in Germany struggling with datastructures and algorithms in University..
A big, big thank you, if I pass the test in 4-6 weeks, I make sure to donate something to you.
Thank you very much for those kind words.
How did you get the N^2 - N in N^2 - N - ((N-1)(N)/2)? @6:00
Pretty easy, look at the upper bound of each sigma sign and calculate how much it runs for the inner loop, therefore, for the first sigma sign for example: Σn from i=0 to n-1, means "upper bound minus lower bound + 1":
n - 1 - 0 + 1 = n. Now you know how much it runs for the inner loop, multiply this with the inner runtime which is "N" (as you stated it) and you get n*n = n^2. Replicate this for the last two sigma signs and you get the result. Rule/Note: Σi from i=0 to n can be solved by using the gaussian summation rule which is:
Σi from i=0 to n = n(n+1)/2 while you have to replace the 'n's in the gaussian summation rule by replacing the n with the upper bound of your sigma sign. Thats it!
ArmaganVideos thank you!
Yo Randerson! I passed the exam! Please contact me with your Paypal or something similiar, I want to thank you. We can work on designs for your channel aswell, instead of a donation.
Much love from Germany!
One of the most meaningful videos I have seen lately. Thank you very much !
I LOVE IT!
I for example am pretty bad at math. I take this algorithm/complexity course without knowing basic Analysis or anything. And you always write NOTE: and explain what exactly you do to those summation formulas! That's freaking awesome man!
Keep up the good work!
+Martin Habsburger thanks!
Martin Habsburger thanks!
you just don't know how much you helped me with this video, thank you very much sir.
Currently taking an Algorithm Design course at school, Thank you so much for these videos!!
you've made this really easy to understand, writing down all the rules and stuff. you're really helpful man thanks :)
Thank you!
Thank you for all of your videos. Incredibly helpful!
Thank you very much I was stuck in a question of algorithms and data structures. May God bless you.
This video solved many of my problems! Thank you really!
this video worth gold , good job sir , thank you :D
Your videos are the best - period.
Thanks !!!
Thank you, that is very good tutorial. I like delicate explanation and help me a lot.
Do You have more videos of Time complexity of code fragments?
does the n + m + 1 only apply if you have a constant number? what if its the summation ranging from n, to j where j = 1. then instead of a constant number, it's j(j +1)? do you substitute 1 with j(j+1)?
Exactly what I was looking for! Keep it up
Anish, that's good to hear and thanks !
I wish not only did we go to school together but we studied together.
+Hughbert HanLon
You can see more videos on time complexity below:
1) ua-cam.com/video/UwWTE3u7FFk/v-deo.html
2) ua-cam.com/video/AL7yO-I5kFU/v-deo.html
You’re my hero
Thank u from the bottom of my heart 😭❤️❤️❤️❤️❤️
Haha thanks, I know this stuff can be hard to understand sometimes, but keep learning it will all be worth it in the end.
Does the summation proof only apply for for loops? Can we do it with while loops?
Great Work Clear Explanation... ❤
Had to log in just to thank you. I don't usually but Good ass video brehhh. Lol you teach very well and your videos are criminally under-viewed.
+benja303 thank you for taking time to leave such a pleasent comment.
Dude these videos literally saved my ass thank you so much
Great explanation!
Thank you so much!! this helps me a lot, keep uploading :)
+kokunutt thanks,
I plan to keep uploading!
very good video, thank you !
you're a goat man, please let me know if theres any place I can support you
Thank Honk, I appreciate that !
I also appreciate that you would like to support me, below are two places where you can do that:
1. PayPal:
www.paypal.com/donate?token=vjtNH8bGGvC8zN90Xc9C3bC3PR95cQM19ncFnz9sqdejeFnJNdW9BWWv4MUHQYpyO4xusuBo5wBwuwHO
2. Patreon.com:
www.patreon.com/randerson112358
Thanks for watching !
Dude, you're amazing
YESSSS thank you much appreciated!!!!
Hello.. Thanks for the tutorial. I'm a bit confused. It's right that sum of i = n(n+1)/2 .. But in the last of the board u write n(n-1)/2.. Is it corect? Bcs i do calculate the answer should be (n2-3n) / 2 ..
Thanks for the video anyway.. I really understand it now:)
Thank you, sir.
Thank you soooo much my cs course makes so much more sense now
What class are u watching this for? I'm trying to make sense of Foundations I: Discrete Structures at OSU.
Great example! Thank you!
+Daniel Mihu thanks for watching!
your the best man, i love you
Thanks Salah !
Hey man
Can you specifically define in a new video about worst, best, and average time complexity of an algorithm using for loop
6:03 why do you get n^2? what's he simplifying or combining?
i was confused here as well. i believe it is because the loop runs N times, and it adds N each time, therefore the sum would be N*N.
You can also use the formula from before. You would need to factor out the n and would be left with n * (the summation). You can then use the formula he erased first, (n - 1) + 0 + 1 = n. Remember we factored out the n, so we have to multiply it back in, so n*n = n^2
Excellent explanation!!
Thanks!
Great stuff!
Math guy here, those are some crisply written sigmas my friend.
Thank you
Would this be considered an actual proof?
You are the best, thank you man
Thank you Victor ! I may not be the best, but I am glad that my explanation of the problem was helpful to you and I think it's always good to get different perspectives from different people to solve a problem.
Just know that I truly appreciate your comment, thank you !
Thanks !!
can you explain how to get the best and worst results ?
how does (i + 1) become i - 1 @4:06?
thank you very much.
*Wouldn't be the upper bound of the first summation "n" ?*
Since your first loop header also means :
_for(int i = 0 ; i < n ; i++) { // .. }_
which checks for n-0+1 number of times, which equals to n+1 and then *the summation formula for the inner loop would begin from the lower bound i = 0 to the upper bound n* ( which is 1 less then the outer loop header ) and so on...
Or am I missing something?
Hi, I am not sure I understand your question, but the outer loop runs O(n) time.
How come? Do you mean the header or the body? Doesn't the outer loop *header* run for n+1 times?
If an algorithm runs n+ 1 then it is O(n).
Another example would be if an algorithm runs n+ 45 or 2n or 2n +1 all of those equations are O(n).
The outer for loop itself would technically n+1, and everything within the for loop (if it is a constant) would run n times, because the loop runs from i=0 to n-1.
For example if n= 3, then our loop runs
i=0
i=1
i=2
So it runs 3 times or n times, and same goes for anything within the loop that is a constant.
You are right but I was just talking about the exact number of times. I mean without asymptotic notation. So shouldn't your upper bound at the very first summation formula be n instead of n-1?
Ah, I see.
No the summation is correct because we are looking at 'loop body' which is within the outer loop and the inner loop. If I was only looking at the outer for loop itself then yes it runs n+1 times exactly, but any constants inside that loop would run n times.
The outer for loop itself runs n + 1 times only because it has to check the condition for when to stop.
Can you do something like this but with triple for loop and the third loop is k
thank you so much
awesome thank you
do you have any other videos regarding Algorithms ?
+Sheikh Waleed Naeem
Here is a playlist:
ua-cam.com/video/4XkHbNi1ZL4/v-deo.html
Thnank you !
Thank you so mucchhh
Love you so much ^^
Thanks!
Great and well don but I am still confusing about the last step why did you make it n^2 and discarded the other part of the last expression thanks
I am not sure which part you are talking about specifically, but I am guessing at @5:58
Here the equation was:
Σn - Σ1 - Σi
I said that was equal to:
n^2 - n - [ (n-1)(n) / 2]
Converting Σn to n^2:
Σn = n x Σ1 = n x n = n^2.
Converting Σ1 to n:
Σ1 = n, For example if n=5 then the summation from i=0 to n would be (1 + 1 + 1 + 1 + 1 + 1 = 6)
and
Since our value goes to n-1, in this case if n = 5 the summation would look like this (1 + 1+ 1+ 1+ 1 = 5)
So in the second case we see that the value we get back is n or in this case the number 5.
NOTE: Σ means summation from i=0 to (n-1)
NOTE: Σ1 means summation from i=0 to (n-1) of 1
NOTE: Σn means summation from i=0 to (n-1) of n
I hope that helps !
randerson112358
These videos seem great, but I got lost in the summation notation. In particular, what you just tried to explain above. I watched some basic summation notation videos on UA-cam but none went over what you did in this video. Do you know of a good youtube video to watch, so I can better understand this video? Thanks!
Hi,
Thanks for the comment. What is it that you don't understand in this video, maybe I can help you.
Also I have more videos on topics like this below:
Running Time of Code Fragment:
ua-cam.com/video/h3ld8FbD7FU/v-deo.html
Big-Oh of the code segment:
ua-cam.com/video/nbtPmejK_C8/v-deo.html
Prove Time Complexity of the following Program:
ua-cam.com/video/UwWTE3u7FFk/v-deo.html
Compute the Time Complexity of the following Code:
ua-cam.com/video/AL7yO-I5kFU/v-deo.html
Thanks;
randerson112358
Confused about what you did at 6:00. Maybe I'm missing some rules of summation, but I don't know how you simplified those summations.
Yes, I used summation properties/formulas:
en.wikipedia.org/wiki/Summation
I have a video on Summations (hope it'll help):
ua-cam.com/video/hXeb8cM5o_0/v-deo.html
I am not sure which part you don't understand exactly, for example if it's how I was able to move over the summation notation from sum( n - 1 - i) = sum(n) - sum(1) - sum(i) or if it's how I got the following:
sum(n) = n^2 ,
sum(1)= n,
sum(i) = (n-1)(n) / 2.
Where sum() is the summation from i=0 to (n-1)
So first I used the property of summations (You must understand properties of summations to work with them):
sum( n - 1 - i) = sum(n) - sum(1) - sum(i) [by propery of summations]
= n * sum(1) - sum(1) - sum(i) [Here I was able to take out the n, by property of summation]
= (n * n) - n - sum(i) [ sum(1) = n, by summation formula from i=0 to n]
= (n ^2) - n - sum(i) [ just making the equation look nice by multiplying the n's]
= (n ^2) - n - (n-1)(n-1 + 1) / 2 [sum(i) = (n-1)(n-1 + 1) / 2, by summation formula]
NOTE: Their is an formula for
sum(i) from i=0 to n = (n)(n+1)/2, notice the similarities,
I plugged in "n-1" for "n".
= (n ^2) - n - (n-1)(n) / 2 [Just did some addition ]
I hope that helps;
randerson112358
Hello. What if I have to write the time for line 1, line 2, and line 3 individually? :(
Bro I’m in the same situation as you did you manage to me pass this class or find videos lol
What if loop condition is only less than (
then subtract 1
good stuff !!
Thank you 😊
Super helpful, thanks :)
+corporalwaffles thank you very much !
+corporalwaffles thank you very much !
+corporalwaffles thank you very much !
+corporalwaffles thank you very much !
+corporalwaffles thank you very much !
It doesn't affect the final answer but on your last step you changed a - to a + which should give you (n^2 -3n)/2
I am not sure which step you are referring to.
Before the final answer I had the following equation:
[ (2n^2 - 2n) / 2 ] - [(n^2 - n)/ 2]
Simplifying this would give:
[ (2n^2 - 2n) - (n^2 - n)] / 2
Simplifying the above would give:
[ 2n^2 - 2n - n^2 - (- n) ] / 2
Simplifying the above would give:
[ 2n^2 - 2n - n^2 + n ] / 2
Simplifying/rearranging the above would give:
[ 2n^2 - n^2 + n - 2n ] / 2
Simplifying the above would give:
[ n^2 + n - 2n ] / 2
Simplifying the above would give:
[ n^2 + - n ] / 2
Simplifying the above would give:
( n^2 - n ) / 2
Please let me know if I was wrong in any of theses steps or if you missed something or if this was not the part of the equation you were talking about and thanks for watching !
thanks a lot for this video I really appreciate it but I don't get the n^2 at 6:05
Thanks in advance.
The first summation is equal to n^2.
I think he is asking how you arrived to that conclusion...I have the same question
Summation rule : upper(n-1) by n = n*n = n^2
Wouldn't it be (n^2-n) and the next one [summation of 1] is n-1?
see, you know its n-m+1 , here its (n-1) - 0 +1 and we multiply that by n )cuz its sum of n , so it Will be ((n-1) - 0 +1) n ,,, so it be come (n)n and that equals@@Crzynoob to n^2 . ^_^
this might be a stupid question, but why do you use theta ??
This isn't a stupid question. To help explain why here is a video that I have on Big Theta that will explain what it is, and then you will know why I use it !
ua-cam.com/video/Vzqaz4MDGvc/v-deo.html
The short answer is because it's the tight bound.
Thanks for watching !
randerson112358
awesome
thank you very much ^_^
Thank you for the very nice comment !
thanks bruh
Thanks for watching!
Cool video, but I still can't understand :((
Something is wrong with me or maths...
finally a video that doesn't begin with "Ello Frents duday we are looking ad comblexity of alogoritum."
Well you gotta give it to them... people from India are very keen about their programming ;)
"THAT'S RACIST!" I feel you bruh
greeaaaat video
Thanks Angela!
g8t work....
Thanks !!
6:20 n^2 - n that seems fishy
i think its n^2 - 2n -1
summation of i = 0 to n -1 and n is n (n -1)
Thanks for the comment but after checking my math everything looks correct, if you think it's wrong could you please show the math ?
how did we get n^2 - n ... ??
I don't know which part of the video that you are referring to.
at 6:05
That's what the summations are equal to.
sum from i=0 to n-1 of n = n^2
sum from i=0 to n-1 of 1= n
To figure out how those are equal you can use the summation formulas. I have the formula in the video @4:15
ua-cam.com/video/4XkHbNi1ZL4/v-deo.html
For sum from i=0 to n-1 of 1= n
m = 0
n = (n -1 )
Then plug in the values for (n - m + 1) = ( (n-1) - 0 + 1) = n - 1 + 1 = n + 0 = n
sum from i=0 to n-1 of n = n^2
This is just n * (sum from i=0 to n-1 of 1) = n * n = n^2
I hope that helps
Thanks for watching;
randerson112358
still confusing becoz formula you told for summation solving was n-m+1 then how get we n^2 over here ??
Do you understand summations ?
If not I would probably start there. Look up summation operations and formulas.
Okay let me show you how I got n^2.
summation from i=0 to n-1 of n
= n * [ summation from i=0 to n-1 of 1] (by summation properties)
= n * [(n-1) - 0 + 1 ]
= n * n
= n^2
I have a video on Summations if that is what you do not understand:
ua-cam.com/video/hXeb8cM5o_0/v-deo.html
Isn't this Big Oh, instead of Big Theta?
+Vlatko Ristovski It's both
Wow, you are fast, btw great lecture :D
+Vlatko Ristovski thank you very much
I dont get why its n^2 v.v
same problem
At 5:35 did you mean to say
n-1 n
∑ i = ∑ i
i=0 i=1
No I did not.
@@randerson112358 Then how will
n n
∑ i = ∑ i
. Could you please explain?
i=0 i=1
@@swaytha7
From my video:
n n
∑ i = ∑ i
i=0 i=1
Let n = 3 for example, then we get the following summation:
3 3
∑ i = ∑ i
i=0 i=1
The first summation = 0 + 1 + 2 + 3 = 6
The second summation = 1 + 2 + 3 = 6
Both are equal.
@@randerson112358 Ah got it :). Thanks so much for the video and clear explanation. Really helpful.
I love that you made this video but there seem to be some clear mistakes, no? Like some of your jumps and your note about the summations being equal when they clearly were not.
sory of confused me more lol
You didn't add the Sum(1) from i=0 to n-1...great video though!