Time Complexity of Code Using Summations

[@TaarLps]

Finally someone that actually does something else than "Well you see here, it is in O(n^2)."

[@armaganvideos]

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.

[@randerson112358]

Thank you very much for those kind words.

[@GregEads]

How did you get the N^2 - N in N^2 - N - ((N-1)(N)/2)? @6:00

[@armaganvideos]

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!

[@GregEads]

ArmaganVideos thank you!

[@armaganvideos]

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!

[@martinhabsburger4929]

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!

[@randerson112358]

+Martin Habsburger thanks!

[@randerson112358]

Martin Habsburger thanks!

[@imersaovisual]

Your videos are the best - period.

[@randerson112358]

Thanks !!!

[@amrmoneer5881]

you've made this really easy to understand, writing down all the rules and stuff. you're really helpful man thanks :)

[@randerson112358]

Thank you!

[@vasanth23]

One of the most meaningful videos I have seen lately. Thank you very much !

[@feyisayo]

Currently taking an Algorithm Design course at school, Thank you so much for these videos!!

[@yaldayazdanpanah2104]

This video solved many of my problems! Thank you really!

[@clockus8023]

Thank you very much I was stuck in a question of algorithms and data structures. May God bless you.

[@baraasaad2366]

you just don't know how much you helped me with this video, thank you very much sir.

[@jg12357]

Thank you for all of your videos. Incredibly helpful!

[@shyom1d676]

You’re my hero Thank u from the bottom of my heart 😭❤️❤️❤️❤️❤️

[@randerson112358]

Haha thanks, I know this stuff can be hard to understand sometimes, but keep learning it will all be worth it in the end.

[@honk-]

you're a goat man, please let me know if theres any place I can support you

[@randerson112358]

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 !

[@movieshome2387]

Great Work Clear Explanation... ❤

[@EpicVideoGameMaster]

Thank you soooo much my cs course makes so much more sense now

[@lukeleedy3713]

What class are u watching this for? I'm trying to make sense of Foundations I: Discrete Structures at OSU.

[@slomotionaction]

I wish not only did we go to school together but we studied together.

[@aminelagab4830]

this video worth gold , good job sir , thank you :D

[@thetedmang]

Math guy here, those are some crisply written sigmas my friend.

[@anishprabhu8592]

Exactly what I was looking for! Keep it up

[@randerson112358]

Anish, that's good to hear and thanks !

[@randerson112358]

+Hughbert HanLon You can see more videos on time complexity below: 1) kzbin.info/www/bejne/i6i6hXhpqpx5fM0 2) kzbin.info/www/bejne/d32aqoJjfpqefLc

[@FireboxTrainingCourses]

Excellent explanation!!

[@randerson112358]

Thanks!

[@flying_Color]

Thank you, that is very good tutorial. I like delicate explanation and help me a lot.

[@victorasmad7305]

You are the best, thank you man

[@randerson112358]

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 !

[@benja303]

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.

[@randerson112358]

+benja303 thank you for taking time to leave such a pleasent comment.

[@petermcgill3405]

Dude, you're amazing

[@banevuk890]

Great explanation!

[@CaptainAwesome923]

Dude these videos literally saved my ass thank you so much

[@Anne-ug4jv]

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)?

[@danielmihu1552]

Great example! Thank you!

[@randerson112358]

+Daniel Mihu thanks for watching!

[@dimanxyou93]

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

[@randerson112358]

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 !

[@UdaySagarReddyMeka]

Thank you so much!

[@randerson112358]

Thanks for watching and commenting.

[@kokunutt76]

Thank you so much!! this helps me a lot, keep uploading :)

[@randerson112358]

+kokunutt thanks, I plan to keep uploading!

[@HughbInc]

Do You have more videos of Time complexity of code fragments?

[@salahelwerfally8810]

your the best man, i love you

[@randerson112358]

Thanks Salah !

[@rezzuu]

good stuff !!

[@randerson112358]

Thank you 😊

[@unix.geektarektalaat1631]

can you explain how to get the best and worst results ?

[@nitsalnand]

Hey man Can you specifically define in a new video about worst, best, and average time complexity of an algorithm using for loop

[@brianramaswami9889]

6:03 why do you get n^2? what's he simplifying or combining?

[@mire_cs]

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.

[@andrewamado5729]

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

[@weezybusy]

Thank you, sir.

[@ProfessionalTycoons]

very good video, thank you !

[@freesoul2677]

Thank you

[@jingjang21]

Great stuff!

[@Burak-pl1jl]

*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?

[@randerson112358]

Hi, I am not sure I understand your question, but the outer loop runs O(n) time.

[@Burak-pl1jl]

How come? Do you mean the header or the body? Doesn't the outer loop *header* run for n+1 times?

[@randerson112358]

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.

[@Burak-pl1jl]

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?

[@randerson112358]

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.

[@kokalti]

Would this be considered an actual proof?

[@iPhanman]

Does the summation proof only apply for for loops? Can we do it with while loops?

[@aaallami]

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

[@randerson112358]

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

[@kevinryzack5712]

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 KZbin 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!

[@randerson112358]

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: kzbin.info/www/bejne/nmTPlWt8l6lqfLc Big-Oh of the code segment: kzbin.info/www/bejne/pJPXgaCbn7CSeZo Prove Time Complexity of the following Program: kzbin.info/www/bejne/i6i6hXhpqpx5fM0 Compute the Time Complexity of the following Code: kzbin.info/www/bejne/d32aqoJjfpqefLc Thanks; randerson112358

[@kevinryzack5712]

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.

[@randerson112358]

Yes, I used summation properties/formulas: en.wikipedia.org/wiki/Summation I have a video on Summations (hope it'll help): kzbin.info/www/bejne/nonIk2uZgpqilZI 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

[@dawid7260]

Can you do something like this but with triple for loop and the third loop is k

[@ge4149]

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:)

[@MovieZaddy]

this might be a stupid question, but why do you use theta ??

[@randerson112358]

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 ! kzbin.info/www/bejne/jKvUkq1qgql6rMU The short answer is because it's the tight bound. Thanks for watching ! randerson112358

[@denverrivera4968]

Thank you so mucchhh

[@mrpwnr24]

YESSSS thank you much appreciated!!!!

[@noreenmekky230]

thanks a lot for this video I really appreciate it but I don't get the n^2 at 6:05 Thanks in advance.

[@randerson112358]

The first summation is equal to n^2.

[@CabCallawayMusic]

I think he is asking how you arrived to that conclusion...I have the same question

[@user-ch2ni9lt9i]

Summation rule : upper(n-1) by n = n*n = n^2

[@Crzynoob]

Wouldn't it be (n^2-n) and the next one [summation of 1] is n-1?

[@VIp2011x]

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 . ^_^

[@DOC0OC]

thank you very much.

[@bobjames1521]

finally a video that doesn't begin with "Ello Frents duday we are looking ad comblexity of alogoritum."

[@nickp7526]

Well you gotta give it to them... people from India are very keen about their programming ;)

[@Y0d3lingy3ti]

"THAT'S RACIST!" I feel you bruh

[@MrAlikdv]

Thanks !!

[@corporalwaffles]

Super helpful, thanks :)

[@randerson112358]

+corporalwaffles thank you very much !

[@randerson112358]

+corporalwaffles thank you very much !

[@randerson112358]

+corporalwaffles thank you very much !

[@randerson112358]

+corporalwaffles thank you very much !

[@randerson112358]

+corporalwaffles thank you very much !

[@TimStark]

how does (i + 1) become i - 1 @4:06?

[@WaleedNaeem]

do you have any other videos regarding Algorithms ?

[@randerson112358]

+Sheikh Waleed Naeem Here is a playlist: kzbin.info/www/bejne/aonOeZWEnpaNgpY

[@WaleedNaeem]

Thnank you !

[@bharlesCabbage]

Hello. What if I have to write the time for line 1, line 2, and line 3 individually? :(

[@jatindergill1875]

Bro I’m in the same situation as you did you manage to me pass this class or find videos lol

[@RawwestHide]

thanks bruh

[@randerson112358]

Thanks for watching!

[@brettmccausland880]

awesome thank you

[@anyod5625]

Love you so much ^^

[@randerson112358]

Thanks!

[@MuhammadKashif-ty4pn]

awesome

[@unknownunknown8699]

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)

[@randerson112358]

Thanks for the comment but after checking my math everything looks correct, if you think it's wrong could you please show the math ?

[@ayushjindal6885]

What if loop condition is only less than (

[@randerson112358]

then subtract 1

[@battsogtbatgerelt1583]

thank you very much ^_^

[@randerson112358]

Thank you for the very nice comment !

[@alirezaayinmehr7854]

Cool video, but I still can't understand :(( Something is wrong with me or maths...

[@angelamunyao7877]

greeaaaat video

[@randerson112358]

Thanks Angela!

[@parvathydharmarajan4180]

g8t work....

[@randerson112358]

Thanks !!

[@swaytha7]

At 5:35 did you mean to say n-1 n ∑ i = ∑ i i=0 i=1

[@randerson112358]

No I did not.

[@swaytha7]

@@randerson112358 Then how will n n ∑ i = ∑ i . Could you please explain? i=0 i=1

[@randerson112358]

@@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.

[@swaytha7]

@@randerson112358 Ah got it :). Thanks so much for the video and clear explanation. Really helpful.

[@user-dj9iu2et3r]

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

[@ristovskiv]

Isn't this Big Oh, instead of Big Theta?

[@randerson112358]

+Vlatko Ristovski It's both

[@ristovskiv]

Wow, you are fast, btw great lecture :D

[@randerson112358]

+Vlatko Ristovski thank you very much

[@TheZainullahkHan]

how did we get n^2 - n ... ??

[@randerson112358]

I don't know which part of the video that you are referring to.

[@TheZainullahkHan]

at 6:05

[@randerson112358]

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 kzbin.info/www/bejne/aonOeZWEnpaNgpY 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

[@TheZainullahkHan]

still confusing becoz formula you told for summation solving was n-m+1 then how get we n^2 over here ??

[@randerson112358]

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: kzbin.info/www/bejne/nonIk2uZgpqilZI

[@linaa6681]

I dont get why its n^2 v.v

[@VIp2011x]

same problem

[@rajawikiaa]

You didn't add the Sum(1) from i=0 to n-1...great video though!

[@bushraw66]

thank you so much