Recitation 1: Asymptotic Complexity, Peak Finding

MIT 6.006 Introduction to Algorithms, Fall 2011
View the complete course: ocw.mit.edu/6-006F11
Instructor: Victor Costan
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@insightful2074]

I swear, he is the coolest TA I've ever seen in my life!

[@GoogleUser-ee8ro]

I just love those recitation sessions (not just for this course, almost all EECS courses have them). They fill in more concrete examples and/or mathematical details to the original lecture. Well done MIT.

[@arketos]

i can't agree more. Sometimes I can't learn in the lectures but i can always learn in the recitations. Because it's gives you solid interaction, not observation

[@TheRealSaintNickNorthside]

Crazy to think that I was flipping pizzas at Little Caesars and taking college algebra in fall 2011, and here I am learning about algorithm complexity 9 years later when this was recorded way back then. Life takes us on a weird journey.

[@6lack5ushi]

bruh idk what I was doing in 2021 but definitely not enjoying a video on asymptotic complexity at 4am on a Sunday morning.... wonder where we end up.

[@lolapalloza183]

Why were you flipping a pizza dude?

[@sibsaurabh]

This recitation class is very helpful and is a necessary supplement to lecture for in-depth understanding. Thanks Victor

[@waynechang1206]

thank you MIT for sharing all sessions for free. Learned a lot from it.

[@bkboggy]

Great TA. Thanks for the presentation.

[@dve845]

@25:00 A much simpler solution is the fact that (n n/2) is picking half the elements out of N elements ... so 2^N must be an upper bound to that, hence O(log(2^n)) = O(nlog(2)) = O(n)

[@artificiyal]

How? Can you explain a bit more?

[@user-bb1ew6kj7h]

When it comes to (n n-2), 2^N is an upper bound for sure, but there is a tighter upper bound. I don't think this way is great enough in all (n i) case.

[@crypticamalgam9695]

These MIT videos are great, but I hate it when someone in class asks or answers a question and it's inaudible in the closed caption

[@gauravmufc1]

The TA in mit is much more educated and versed in the subject than the head of department in my college.

[@blo0mfilter868]

same bro

[@benwade647]

Same😓

[@MajedDalain]

so good, It helped to understand the omega, theta and O. thank u so much

[@dylancutler1978]

Victor is a good educator

[@veramentegina]

thank you MIT!! excellence in everything!

[@scottzeta3067]

When he is asking everyone whether following I really want to anwser I am. This lesson really has magic can let me keep attention on it, compare with my university.

[@garychan4845]

at 53:30, TA said M in the original equation will be replaced by lg(m) if 1-D peak is used instead. But I think not only that M is changed, the M in the recurrence (i.e. the M in T(N/2,M)) and the base case are also changed to lg(M) as well. Am I correct?

[@briscoelang2436]

Good explanations from the future phd

[@user-qs8ct8ws5u]

super helpful recitation. It solve me many confusions from the class

[@manaspeshwe8297]

He says good question in a sarcastic way LOL.

[@roylee3196]

is there a channel for us to improve the subtitles? I've noticed a couple of mistakes, for example at 39:32 , its supposed be T(n/2^i) instead of T(n/2^n).

[@mitocw]

+Roy lee You can send an email with subtitle correction(s) via the Contact Us form at ocw.mit.edu/jsp/feedback.jsp?Referer=. Depending on how much you want to do, the subtitle files (.srt) are available on our site at ocw.mit.edu/6-006F11. We welcome corrections to them. :)

[@nalinitamilmani]

Excellent....Awesome...You really explained well...Kudos to you guy.

[@justinbieber9656]

Istg he is pretty good for a TA. Grab a tub of popcorn and it is pretty fun to watch over weekends. :')

[@free-palestine000]

victor is OUR ta now

[@samratroy1234]

"No answer means yes..." reminds me of my profs ...

[@veipuniilana1842]

I will take that as Yes

[@nguoikechuyenlichsu6472]

It is so great, I love exercise class

[@yassergaber6428]

Session Notes: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/recitation-videos/MIT6_006F11_rec01.pdf

[@edward7282]

this guy explains better than my professors at uni, wow

[@susguy4469]

Can the Big Theta of a function have the same upper bound and lower bound(same constant factor)? For example: the function n^2 = Big-Theta(n^2) could mean n^2

[@ramiyer6810]

I guess you could but that wont be useful because it represents a very specific case of g(n) = theta(g(n)). This is true but whats the point of the asymptotic notation if it is not making your life simpler.

[@xiaoweidu4667]

very good quality recitation !

[@ajai.a2374]

Thank you!

[@brngylni]

This is really perfect.

[@DivinityStripes]

At the end did they say the algorithm using the variation would be faster? I swear it would be incorrect and wouldn't be able to return a peak.

[@erichlf]

DivinityStripes he said that we would look at complexity forest because of it isn't faster then who cares if it works or not. If out works then we will check if it is correct.

[@stevenzhao6647]

Yeah, I agree - the algorithm will not guarantee that the result would be a 2D peak. The TA should have clarified that it is efficient but incorrect.

[@funyunonion37732]

This dude is hilarious, I would be dieing in this class

[@florentynastone3673]

Thanks, great (and very cute :D) TA!

[@stefantoljic5013]

Beautiful! :D

[@boluaygepong5920]

@26:40 "Factorials grow exponentially". Hmmm, I wonder what the answer is?

[@ShubhamSinghYoutube]

His name was Victor sin, but he changed it to costan.

[@mond2440]

i dont get it when the sub array becomes 1 element its more like the worst case of that algorithm instead of theta

[@spacesuitred3839]

victor THE CHALKBREAKER :) 7:35 30:41

[@lilyyeh8607]

thank you

[@Draven1334]

SIMPLY THANK YOU

[@vedchoudhary9519]

31:15 How did it become Theta(n) ? Yeah, it has an upper bound of order n, O(n), but what about lower bound?🤷🏻‍♂️

[@mahmoudihocine2837]

Can any one explain how the simplification work in the log ? how were ln 5 in the base and power of 100 thrown away? @22:13

[@punstress]

Is the algorithm being applied correctly, or described correctly, or am I not getting it? Start in middle, look at neighbors, if local peak halt, else recurse T(n/2), is what he wrote. Recurse T(n/2) means to me, start in the middle of one of the halves, and I guess it doesn't matter which one, and check its neighbors, if local peak halt, else recurse by starting in the middle, n/4. What I'm seeing him do follows that up to the recurse T(n/2). He doesn't start in the middle of one of the halves, he starts at the beginning, i.e., the larger neighbor of n/2. It makes more sense to do it that way but it's not the way he wrote out the algorithm, is it?

[@jeanjean6739]

I know it's quick but I love you

[@edenender]

What is the practical aplication for all this discussion ?

[@samanthabrady6498]

This kid is adorable.

[@purleedef]

How come he can get rid of the base at 23:31? I thought he did it at 22:11 because when n gets larger, log(ln(5)) is just a trivial number that doesn't have much impact on the result. But at 23:11 it affects the calculation itself before we make that assumption about the scalability Couldnt you do the same strategy as the earlier problem without getting rid of it? I end up with: log(100 log(n)) / log(ln(5))

[@ananyakumar]

It's not about whether it has an impact or not, log(ln(5)) is a constant value that does not affect the upper or lower bounds. Hence, we can eliminate it from our final solution. What you've suspect to be the reason log(ln(5)) was dropped in the first example is actually true for any function that contains n. For example, look at 31:09 - we reject log(n)/2 because it exponentially smaller than 2^n. In this case, the reasoning that log(n)/2 is just a trivial number that doesn't have much impact on the result as n increases is correct. Hope this helps!

[@markwilliamsphl]

How many hours does MIT EECS meet their students in these recitation sessions per week? Is it always 1 hour lecture, 1 hour recitation? Do they have a lab session in this class?

[@mitocw]

Lectures: 2 sessions / week, 1 hour / session Recitations: 2 sessions / week, 1 hour / session See ocw.mit.edu/6-006F11 for more info. Best wishes on your studies!

[@ikram3105]

28:34 *how does the root in denominator cancels out when the exponential is only N ???*

[@puravhs36]

The denominator gets squared(and the square(^2) removed from the previous step)

[@spartacusche]

minute 36, why did he uses theta in the analysis of the peak find instead of Big-O

[@julian92]

Because in some cases O is the same as Theta

[@malharjadhav8404]

@2:29 6006 was intentional

[@ashutoshtiwari4398]

the problem of log( ( n n/2 ) ) would be much simpler if you wouldn't use approximation formula. Just open the factorials and check the highest power of n.

[@victoriajiang892]

the log() won't go away if you just simplify what's in the parenthesis

[@tarunkushwaha3922]

he is cool at words. :D

[@ayyashC]

Can someone please explain the 21:48 reduction ? why did the exponent got simplified ?

[@roylee3196]

+Ahmad Ayyash (Ash) it's because in log-arithmetics, log(n^2) = 2 log(n), you can bring down that exponential as a multiply, and since its a constant, hence it's non-significant and neglect-able.

[@ministryoftruth596]

Yes, but what happens when you have log(n)^2?

[@zeronothinghere9334]

@@ministryoftruth596 That is the same as log(n) log (n) so you can add them to log(n*n) = log(n^2) = 2 log(n)

[@victoriajiang892]

@@zeronothinghere9334 why is log(n)*log(n) equivalent to log(n^2)?

[@zeronothinghere9334]

@@victoriajiang892 Was my mistake.

[@Ankit9296]

what if no. of array is even how can we decide middle

[@Aziz-wl1xf]

You round the quotient.

[@NovaMenteMedia]

I'm sorry at 24:56 why N is over N / 2 isn't (N ^ N)/2 ?

[@AbhimanyuAryan]

don't wry he solved it wrong way

[@GianLucaDegani]

no, because it's a binomial coefficent

[@arpitagarwal016]

Why did he multiplied O(M) in the end? how did that come?

[@horriblefate]

Find maximum element in just one column = M The (maximum) number of column that you need to check = log N Total = for the (log N) number of columns, you check all M elements on each column = M * log N

[@wazaabazaa]

rows*columns where M was the columns

[@damyant_jain]

Can someone please explain the difference between (log n)^100 and log (100)^n. This was during 22:10.

[@ritik5356]

(log n)^100 = (logn)*(logn)*... 100 times, log (100)^n = log (100 *100 *100 *... n times) = n*log(100)

[@edmbootcamp6188]

i see i am not the only one who purchased every shirt from the pure pwnage web shop. Hello my brother

[@odgiiv1]

Why does exponent goes out at 22:11

[@ikram3105]

it was a constant. Would have come before log and then not considered because *a constant.*

[@shasankaborah2700]

actually i don't exactly understand what is complexity in algorithms and how to find them?

[@Quisl]

Its the number of steps (for example CPU cycles or time spent calculating) that are required to run and finish an algorithm.

[@MehulKumar_m3huL]

Dominant portion of function which depends on input size. Everything else is moh maya ;-}

[@kaliabsurde6215]

hi. thank you for this courses. what is the difference between lectures and recitation lectures?

[@heaven101010]

Hi, you can ask google the exact same question and get a very nice and clear answer from MIT (1st link).

[@unev]

Recitation is a complement to lecture. Whereas lectures are filled with far too many students and far too much material to have ample opportunity for individualized engagement and specific questions, recitation holds smaller numbers of students and is aimed to address anything covered during lecture or individualized studying that is unclear. Recitation is a safe space in which asking questions for cla

[@gauravdjgm]

I am surprised that the person who transcribed this lecture could not make out that Victor is saying Srini, who happens to be the course professor, but instead transcribes as [INAUDIBLE].

[@mitocw]

These captions were generated by a third party. They did not know who the instructor was, when they did these.

[@gauravdjgm]

@@mitocw Oh

[@muratzhankyranbay6427]

sweet

[@mohamedtarek8899]

I am still not convinced as to how recursing on the side with the larger number guarantees us the solution.

[@serhatuyanmis1493]

I suggest you to go look for calculus 1 and if you have time go for calculus 2. There are some expression that you can find the answer of the question.

[@murtazahamid6141]

What would happen if there was more than one peak?? The algorithm would simply find one peak and leave it at that

[@luojihencha]

agree

[@golubhai1910]

question is to find a peak, so its ok to have multiple peaks because we are only searching for a peak. watch 6.006 ist lecture then come to this video you will understand

[@kind03cn]

In 2:23, the part of the function he is writing is "Sin(x+1)" not "Sim(x+1) " right?

[@christopherbuja1027]

yes, it is sin. The reason why is that the sin function ranges from -1 to 1, so it adds noise to to the function

[@oishikachaudhury5519]

How are we just canceling out the base?

[@sapnokiranii]

I want to know this too, did you figure out?

[@sweatysweatson9399]

which time frame are you asking about? 20:00 ?

[@riccardosven]

It's a long time past, but answering for future reference: log_a(b) = log(b)/log(a) so a constant base becomes just a constant multiplicative factor that you can disregard.

[@DrewIsFail]

poor chalk :(

[@userdejjek6243]

Wow. I am not related to this major but. I watched this for 25 minutes and I thought this is little bit hard and The ta is little bit hot.

[@alexanderle1610]

❤️

[@AyushBhattfe]

got the whole thing

[@mathematicalcoffee2750]

Ayush Bhat no one cares

[@AyushBhattfe]

MathematicalCoffee you do :')

[@sniperkyle6152]

9:43

[@c.d.premkumar6867]

15:11: if BigO (log N) is > BigO (1) then the minimum value of N must be equal to 10. I have always had this doubt. Can anyone please clarify.

[@kevinryzack5712]

The professor is wrong at the 13:00 mark. It's not a big deal but it's still theta of x^1.5 as x^1.5 is clearly also a lower bound to the equation: (1+sin(x))x^1.5 + x^1.4

[@user-tk2jy8xr8b]

Probably he should have used sin(x)*x^1.5 + x^1.4

[@rfrost4708]

No he is correct because when sinx becomes -1, the x^1.5 term disappears and we have only the x^1.4 term remaining. x^1.5 cannot be the lower bound as it's greater than x^1.4 in this case.

[@fernandofuentes7617]

@@rfrost4708 wut? -1 and disappears?

[@wpelfeta]

Wait. I don't understand the log log log log joke he says at 22:15. I feel like I'm missing something funny. :(

[@apathyonastick]

Q:What does a theory student say when they're drowning? A: Log log log log. Sounds like "glug" or the noise of bubbles in water.

[@AldarionTheMariner]

apathyonastick And I thought he cries for a log to float on it or something.

[@punstress]

It looks like he is writing x^(1.4) but it sounds like he says "x to the one fourth". Maybe I'm not seeing or hearing him correctly? 11:25 Also he switches between N and n as if they are the same... Sloppy.

[@unknownunknown8699]

This dude looks younger than all my colleagues :)

[@Juan-dc6yf]

Tough crowd

[@AbhimanyuAryan]

this guy is so cool & his writing is OK i have seen people with more miserable handwriting & he sits exactly at back of me in exams......n great thing is i have to cheat from his answer sheet.....in chemistry, electrical, physics exams :p

[@priyanksharma1124]

LOG LOG LOG LOG ......drowning

[@flyfast3837]

what is this O instead of Theta shit?! it's messing with my brain!

[@GutsofEclipse]

People who say that monetary profit is just a corrupting factor should think about what he said here. Why does google care about giving you a fast service? Because in a capitalist system, you have a right to not help them make money. Without a capitalist system of accountability to customers, they'd be okay with making you wait for results, just like the DMV (who should be more efficient according to socialist theory), because there's no penalty to them for doing so. >Just go full Soviet and torture them if they don't get 200 milliseconds! And now you understand why putting leftists in charge of humans rights is like putting child molesters in charge of CPS.

[@DanielPage]

I am calm, I am just telling you as a mathematician and computer scientist (both) I found his comments to be very inappropriate to a course in this subject. I would appreciate you not inferring false statements about my feelings. As somebody who has taught this subject numerous times (in analysis) and at the university level myself as an instructor that is not the way to present oneself with this subject. The point is to emphasize the importance of mathematics in computation as it is required

[@TheMasterfulcreator]

He's making the distinction between math and computer science conventions using a little bit of humor. Honestly the fact that you aren't used to this makes it seem like you are in fact not both a mathematician and computer scientist.

[@swapnildadamode662]

people cant read victors handwriting. And he thinks he teaches good.

[@DanielPage]

I find this TAs jokes to be incredibly arrogant. To segregate your students between the "maths" students and the "CS" students is ridiculous. There is no line to draw when they are one in the same.

[@r17v1]

its a fucking JOKE.

[@troooooper100]

i work as a software developer i dont even know how to do calculus 1 whats your point. i dropped cal 2, i forgot cal 1.

[@surajbiswas256]

1:01 that guy gives me some hope that even mit students can forget 3 yeas past topics...🥹🥹🥹 i am so glad to hear that