HomeЛюди и блогиRelated VideosMore From: randerson112358

Compute The Time Complexity Of The Following Code

942 ratings | 104407 views
Compute the complexity of the following code fragment. Easy Algorithm Analysis Tutorial: https://www.udemy.com/algorithm-analysis/ Recurrence Relation Tutorial: https://www.udemy.com/recurrence-relation-made-easy/ Please subscribe ! Here is an example where you might think the answer should be log n according to the rule of thumb for multiplication/division in loops: https://www.youtube.com/watch?v=13Qb0GUo4Oc&t=25s&list=PLj68PAxAKGoxhAXr-YyjeG9-SyTR5Hm4P&index=27 Here is a pretty simple video on time complexity resulting in O(n): https://www.youtube.com/watch?v=mwAQfKbV51M&t=25s&list=PLj68PAxAKGoxhAXr-YyjeG9-SyTR5Hm4P&index=32 Here is an example of a recurrence relation resulting in O(log n): https://www.youtube.com/watch?v=rrnPp4KmzSI&t=54s&list=PLj68PAxAKGoxhAXr-YyjeG9-SyTR5Hm4P&index=29 Here is a playlist of what I have on algorithm analysis so far: https://www.youtube.com/playlist?list=PLj68PAxAKGoxhAXr-YyjeG9-SyTR5Hm4P ►Website: http://everythingcomputerscience.com/ ►Support this channel on Patreon: https://www.patreon.com/randerson112358 ►Discrete Mathematics Workbooks: (1) Practice Problems in Mathematics - https://www.amazon.com/gp/product/0130458031/ref=as_li_tl?ie=UTF8&tag=everythingc06-20&camp=1789&creative=9325&linkCode=as2&creativeASIN=0130458031&linkId=5ec571a3f11c8356c4a977dd95945e21 (2)Discrete Mathematics Workbook - https://www.amazon.com/gp/product/0130463272/ref=as_li_tl?ie=UTF8&tag=everythingc06-20&camp=1789&creative=9325&linkCode=as2&creativeASIN=0130463272&linkId=722a147e4912843adb18019b7a08a7e4
Html code for embedding videos on your blog
Text Comments (125)
iqi (3 days ago)
im having mid terms this wednesday, you save ma lyf brotha
Rylee Bers (4 days ago)
YOU ARE AMAZING. You explained it clearly unlike my professor.
Israa Kh (16 days ago)
Great man u save my life !
vincent ardyan putra (28 days ago)
Why did you use Big Theta instead of Big O?
HugeFanOfNOFX (30 days ago)
Great explanation, thanks so much!!
randerson112358 (30 days ago)
Thanks!
Timothy Putman (1 month ago)
Dude, nailed it. Thanks for explaining.
randerson112358 (30 days ago)
Thank you !
Desislava Marinova (1 month ago)
How can you determine the worst and best case time complexity scenarios? Many thanks.
Left Fist (1 month ago)
but ur not indian tho..... holy shit
Sam Moses (1 month ago)
i know right :D
Makenna Smith (1 month ago)
Good video!
randerson112358 (1 month ago)
Thank you !
Dariyoush Shiri (3 months ago)
in C5 why we multiply (n+1) by n and why not with n+1? in C3 you said it runs n+1. please explain
randerson112358 (3 months ago)
The loop itself runs n+1 times, but it's being ran within another loop that runs n times. I hope that helps. randerson112358
Gaurav Saini (3 months ago)
Its really an informative video... Thanks a lot :-)
randerson112358 (3 months ago)
Thanks for watching !
babbin tandukar (4 months ago)
i hope ur video saves me tomorrow back paper of DAA ..i will lose a year if i dont make it tomorrow
Alejandro Carranza (4 months ago)
Man you are amazing!! Best tutorial Ive seen in a long time, jeez if only everyone explained like this.
Efi Shtainer (4 months ago)
Loved the content, wish you had a tripod!
Nijat Xaxmas (5 months ago)
you are awsome...... you saved me
Grawlix99 (5 months ago)
London Spitfire C9
Jean Chery (5 months ago)
The equation looks easy to solve.
Saif Ryan (6 months ago)
When 'n' value is 0 then your answer is false???
randerson112358 (6 months ago)
I'm not sure what you are saying if n=0, then n^2 = 0^2 =0. The program would run 0 times or n^2=0^2=0 times.
Saif Ryan (6 months ago)
When value is 0, then not possible to answer is n2. Check it, N value must be greater then 0
randerson112358 (6 months ago)
Nope
Kaleemullah Khan (6 months ago)
sir your video helps me to solve my assignment can you validate it ?
Arun Ajay (6 months ago)
Excellent video. Thank you.
Ryszard Sinius (6 months ago)
Go through the while loop xDD Sounds mighty. Love your explanation
Priyanka Tamil (6 months ago)
Really nice make more simple videos
batabatonica (6 months ago)
I've spent around 2 hours searching for something like this
randerson112358 (6 months ago)
I am glad you find my video and I hope it helped !
Usman Arif (6 months ago)
Excellent explanation Better than my teacher
Anonymous (7 months ago)
Your saving lives bro !! thaanks
randerson112358 (7 months ago)
Haha thank you !
jimmy roberts (8 months ago)
Clear and concise. Thanks for the video!
randerson112358 (8 months ago)
Thank you !
Ayesha Abbassi (8 months ago)
good explanation .. keep it up ..
H Alayed (3 months ago)
how to write compute Time Complexity for this And^2ci) ? in matlab
randerson112358 (8 months ago)
Thank you Ayesha !!
Eric (9 months ago)
No. Thank you!
randerson112358 (8 months ago)
+fracturedude lol thanks for watching!
Robbebeest (9 months ago)
Very informative video. Thank you.
soundofprice (9 months ago)
man you deserve a beer
randerson112358 (9 months ago)
Haha thanks !
Mykola Galian (10 months ago)
Thanks!
AMEER HAMZA (10 months ago)
Amazing
Omar Said (11 months ago)
for people who want to know why is it N+1 not N from 1:10
sahil narkhede (1 year ago)
thanks man.....your video helped me a lot...
randerson112358 (1 year ago)
That's great to hear !
Captain BlackHawk (1 year ago)
nice explaination.....but why it is big thetha rather than big oh???
M (1 year ago)
Thank you so much <3
randerson112358 (1 year ago)
Thanks for watching and the nice comment !
Parmesan (1 year ago)
Can you also say this is Big Oh of n^2?
randerson112358 (1 year ago)
yes
shamima ritu (1 year ago)
I have a question, how the n^2 is related to theta?
Mallory M (1 year ago)
this was super helpful, thanks so much!
randerson112358 (1 year ago)
Thanks Mallory for watching, I am glad the video could help !
vclarke4433 (1 year ago)
I liked the thorough walkthrough and I was able to follow along, but when you were doing all of the time complexity addition at the end I feel like it became harder than it needed to be with all of the grouping substitutions and erasing and replacing. Just add it through next time.
memoonash (1 year ago)
amazing video but i have one question. i=i+1 should've been equal to 2n instead of n.. and same goes for j=j+1 ans sum=sum+1. or not ? as it has two operations to perform. sum and equate.
randerson112358 (1 year ago)
No, we are counting how many times the statement is being executed which is n * n times, or n^2 times. Thanks for watching and the question. randerson112358
David Boateng Adams (1 year ago)
Consider the following algorithm, which takes as input a sequence of n integers a1, a2, . . . , an and produces as output a matrix M = {mij } where mij is the minimum term in the sequence of integers ai, ai+1, . . . , aj for j ≥ i and mij = 0 otherwise. initialize M so that mij = ai if j ≥ i and mij = 0 otherwise for i := 1 to n for j := i + 1 to n for k := i + 1 to j mij := min(mij, ak) return M= {mij } {mij is the minimum term of ai, ai+1, . . . , aj } 230 3 / Algorithms a) Show that this algorithm uses O(n3) comparisons to compute the matrix M. b) Show that this algorithm uses (n3) comparisons to compute the matrix M. Using this fact and part (a), conclude that the algorithms uses (n3) comparisons. [Hint: Only consider the cases where i ≤ n/4 and j ≥ 3n/4 in the two outer loops in the algorithm.] please help
Yakusoku no Ji (1 year ago)
Do you by any chance have an explanation where some of the steps result in log n and stuff? I know general rules for these things and all like "multiplication and division affecting the loop will lead to log n because it skips steps etc." and such stuff but there are so many examples where I am never sure what to do because people often don't explain it fully and properly for beginners. It would be really very much appreciated if you had more of that with thoroughly explained examples where I and others can see how that actually results from calculations. Either the examples I know are to complicated for me as a beginner because I am not familiar with it enough or not they are not explaining enough. (Btw. I am mostly talking about Big Oh).
randerson112358 (1 year ago)
Hi Yakusoku no ji, Here is an example where you might think the answer should be log n according to the rule of thumb for multiplication/division in loops: https://www.youtube.com/watch?v=13Qb0GUo4Oc&t=25s&list=PLj68PAxAKGoxhAXr-YyjeG9-SyTR5Hm4P&index=27 Here is a pretty simple video on time complexity resulting in O(n): https://www.youtube.com/watch?v=mwAQfKbV51M&t=25s&list=PLj68PAxAKGoxhAXr-YyjeG9-SyTR5Hm4P&index=32 Here is an example of a recurrence relation resulting in O(log n): https://www.youtube.com/watch?v=rrnPp4KmzSI&t=54s&list=PLj68PAxAKGoxhAXr-YyjeG9-SyTR5Hm4P&index=29 Here is a playlist of what I have on algorithm analysis so far: https://www.youtube.com/playlist?list=PLj68PAxAKGoxhAXr-YyjeG9-SyTR5Hm4P Thanks for watching; randerson112358
Prathamesh Mestry (1 year ago)
loved it bro.....thumbs up
H Alayed (3 months ago)
how to write compute Time Complexity for this And^2ci) ? in matlab
randerson112358 (1 year ago)
Thanks !
99Songohan (1 year ago)
Hi, first of all, i want to thank you for this great explanation video. im a computer science student and need to learn this topic now. im new in this. so, pls correct me if im wrong. the outer loop ist working until k² > n. right? same for the inner loop. if i multiply both of them, i get the running time of O(n). im not sure. pls help me and correct if im wrong
randerson112358 (1 year ago)
I am not sure that I fully understand your question, but the outer loop runs n times
James Leong (1 year ago)
why c4 not equal to 1?
James Leong (1 year ago)
i knew it ady it is because the external while loop.
Premier Koala (1 year ago)
thank you so much!!
Siva Subrahmaniam (1 year ago)
really love the way u explained abt n+1. In the same way please create a video for (n log n). I cannot find any videos for solving to (log n) in youtube
randerson112358 (1 year ago)
Hi Siva thanks for watching and the suggestion. I am considering putting up a video for O(nlogn). I don't know when if I decide to do it.
tina twine (1 year ago)
Thank you for making such a great video. You made it simple and easily to understand the problem.
randerson112358 (1 year ago)
Thanks Tina for the comment. I used to struggle with this topic and I am glad that my videos can help others. Thanks for watching ! randerson112358
r turan (1 year ago)
why not big O ? why big deta?
r turan (1 year ago)
sorry, I wrote it with a Turkish reading.
Alien Ability (1 year ago)
its theta (Θ) brother not deta.
randerson112358 (1 year ago)
You can use either.
Ola Kaszuba (1 year ago)
This was extremely helpful :) Great explanation. Thank you!
who cares (1 year ago)
hai can i discuss with you problem in reak time ? my facebook id: https://www.facebook.com/xPritamroy47 and please use a stable camera to record :(
Sina (1 year ago)
shouldn't the time of j = 1 be n+1 as well?
randerson112358 (1 year ago)
j = 1 is inside the loop, and the inside of the loop runs n times. The for(...) runs n+1 times, the extra +1 is when it goes and checks if it needs to run again. Example for(i=0; i<2; i++){ //Stuff in here runs 2 times } i=0 then i=1, but wait does the computer know to stop at i = 1 ? The answer is no not yet, but the inside of the loop has run 2 times already, the computer has to check when to stop so i increments one more time and it checks is 2 < 2 the answer is no, so now the computer can stop the loop. So the for(i=0; i<2; i++) runs not 2 times but 3, while the inside of the loop runs only 2 times. Better yet you can test this yourself to see. Below I have code for you in the C programming language to test and see what the value of i is. ------------------------------------------------------- # include <stdio.h> int main(){ int i; for(i=0; i<2; i++){ printf("i=%d in loop\n", i); } printf("i=%d \n", i); return 0; } ---------------------------------------------------- OUTPUT: i=0 in loop i=1 in loop i=2 I hope that helps. Thanks for watching; randerson112358
Sina (1 year ago)
I'm confused :-s j = 1 is inside the loop, and the loop's time is n+1...so how does j = 1's time become n
randerson112358 (1 year ago)
Sina no it should be n
XChange97 (1 year ago)
Very helpful
Anthony Awuzie (1 year ago)
how is (n+1)n = n^2+n ???
randerson112358 (1 year ago)
Here I just multiplied the 'n' by '(n+1)' n(n+1) = n x (n+1) = (n x n + n x 1) = ( n^2 + n) = n^2 + n Hope that helps; Thanks for watching ! randerson112358
Anthony Awuzie (1 year ago)
i love the way you explained why c3 time should be n+1 thanks @1:30
H Alayed (3 months ago)
how to write compute Time Complexity for this And^2ci) ? in matlab
sorriaejogue (5 months ago)
Anthony Awuzie the while loops needs to stop which is when it checks the first false expression right after the last true one. That instruction is the +1.
Darshit Pandit (1 year ago)
perfecto
Abhishek Kulkarni (1 year ago)
saved me! thanks!
AlphaGamer (2 years ago)
1. for(i=1 ; i <= n ; i++) +randerson112358 Can you please tell me the time for these programs i will be very much glad if you do it 4 me. 2. for(j=1 ; j <= i ; j++) 3. for(k=1 ; k <= j ; k++) 4. x++; 1. for(i=1 ; i <= n ; i++) 2. for(j=1 ; j <= n*n ; j++) 3. x++ 1. for(i=n ; i >= 0 ; i--) 2. for(j=1 ; j <= i ; j++) 3. x++ 1. for(i=1 ; i < n ; i = i*2) 2. for(j=1 ; j < n ; j = j*2) 3. x++ 1. for(i=1 ; i < n ; i = i*2) 2. for(j=n ; j > 1 ; j = j/2) 3. x++ 1. i = 1; 2. while(i <= n) 3. { 4. x++; 5. i++; 6. } 1. sumFun(n) 2. { 3. for(i = 0; i<n; i++) 4. s++ 5. } 6. 7. mainFun(n) //T(n)& Big O for this function is required 8. { 9. for(i = 0; i< n; i++) 10. sumFun(i); 11. }
Zu Ab (1 year ago)
i can see you tranna get help for your homework???? hahahahahah
Dhiyaa Abhirama (1 year ago)
LMFAO
Brian Faure (1 year ago)
Bro, you can't just post your homework in a youtube comment
Justin Li (2 years ago)
dude you're awesome, I never learned complexity before, but this makes sense!
TheEnthusiast (2 years ago)
Is there no short hand way to get the answer? Like in an interview situation, would I have to solve all the way out like this?
randerson112358 (2 years ago)
Oops I meant to send you a link to Solving it using summations: https://www.youtube.com/watch?v=4XkHbNi1ZL4
TheEnthusiast (2 years ago)
This links to the same video
randerson112358 (2 years ago)
Yes there is another way, you can use summations for example: https://youtu.be/AL7yO-I5kFU
goodmusic284 (2 years ago)
Thank you so much!!!
wildglorypsn (2 years ago)
very nice video....This is what I was searching for after watching the theory videos :)
TheF1 Sachin (2 years ago)
thanks a lot make more and more video pls :)
randerson112358 (2 years ago)
Thanks man, I plan on uploading more videos !
abhiramreddy005 (2 years ago)
super!!!! thanks a lot
Kistlak Rajapaksha (2 years ago)
Thank U Very Much Bro ! :D
randerson112358 (2 years ago)
Thanks for watching, I hope my video helped
Wanhui Qiao (2 years ago)
Magnificent! I hope our college could recruit you as a lecturer :D
randerson112358 (2 years ago)
+Wanhui Qiao Hi again,  I am not sure what you are asking but I am guessing that you mean one loop can run some number  of times (specifically an odd number) and the other loop can run some other number of times (specifically an even number of times)  In this case n is not the same for both loops since "n" is used to represent the same number.  You would use another variable such as "m" where "m" could be a different number other than "n" In this case instead of getting O(n^2) which is equal to O(n * n) you get O(n * m) where n is even and m is odd or vice versa. Thanks for commenting randerson112358
Wanhui Qiao (2 years ago)
And little question here. If an algorithm runs more times when the n is odd than when n is even, which one should I suppose n to be? The one runs more times?
randerson112358 (2 years ago)
+Wanhui Qiao thank you for your kind words.
mujtaba khalid (2 years ago)
Simply Awsome :)
Mason Cusack (2 years ago)
Finally, someone just freaking explained it! Like like like!
Harsh Mehta (2 years ago)
Superb!!
randerson112358 (2 years ago)
thank you!
Adam Bignell (2 years ago)
Wonderful video. Very useful and direct. Thank you.
Adam Bignell (2 years ago)
+randerson112358 I sent the video to my various C.S. friends (this problem is almost directly on our most recent assignment). You're one of the few people who went through exact accounting (as our prof describes it) rather than purely big O notation
randerson112358 (2 years ago)
Thank you !
fahad shaikh (3 years ago)
thank you just keep the camer and lighting proper next time
Saif Ahmad (3 years ago)
thnx man! so simply and so nicely.
randerson112358 (3 years ago)
+Saif Ahmad thanks for watching.

Would you like to comment?

Join YouTube for a free account, or sign in if you are already a member.