Chapter 3: Characterizing Running Times: Asymptotic Notation

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

You ever get that feeling like there's got to be a faster way to understand something really complex?

Yeah, all the time.

There's got to be some kind of shortcut.

Well, today we're

how to measure how efficient different ways of solving problems are.

What makes one approach better than another?

We call these different approaches algorithms, right?

And understanding how efficient they are, especially when you're dealing with a ton of data, that's like having a superpower.

So it's like if you're trying to find a book in a massive library.

Exactly.

Do you just wander around aimlessly?

Or do you check the catalog and go straight to the right shelf?

Boom, that's the difference we're talking about.

And our goal today is to unpack this whole idea of analyzing algorithms using something called asymptotic notation.

Okay, I'm listening.

We want to break it down, make it clear how computer scientists figure out how well an algorithm performs, especially as the problem gets bigger and bigger.

But we're going to do it without getting bogged down in a bunch of super technical jargon.

Sounds good to me.

So we'll focus on the main tools, big O notation, big omega, big theta.

Those are the heavy hitters.

Exactly.

And we might even touch on little o and little omega.

But the key thing from the get go, the thing to always keep in mind is that we're looking at the order of growth of an algorithm's running time.

Right, right.

As the input size just explodes, like goes through the roof.

That's what we mean by asymptotic efficiency.

It's like you've probably heard people say, oh, this software is faster than that one.

This gives us a really precise language to actually describe that.

Exactly.

It's not about just feeling it out.

It's about having a concrete way to compare.

And it's a way that holds up even when you're dealing with ridiculous amounts of data, like truly massive.

Right, right.

It's not about how fast something runs on your little laptop.

Not at all.

This is about understanding the fundamental scalability of an algorithm.

Like how does it behave as things get really, really big?

Okay, I'm with you.

So let's dive into this idea of asymptotic efficiency then.

It's not just about timing how long something takes on your computer, right?

No, not at all.

Asymptotic efficiency is about analyzing how the running time of an algorithm changes as the input size increases.

Okay.

And it increases without any limit.

We're focused on the rate of that increase.

Does it slow down as the input grows or speed up?

Does it stay the same?

That kind of thing.

Got it.

So it's more about the trend, the pattern.

Precisely.

And this gives us a way to compare algorithms that's much more powerful than just running a few tests.

Like it's a way to understand the inherent nature of the algorithm itself.

Not just how it performs on a specific piece of hardware.

Okay, that makes sense.

So first up is Big O notation.

This is the one you hear thrown around all the time.

What exactly does it tell us?

Big O notation, or OG gives us an upper bound on how a function grows.

In our world, that functions off of the running time of an algorithm.

The formal definition, though, is let's say 5N is our running time.

We say 5N is that we can find some positive constant, call it C dollars, and some starting point for our input size, call it C dollars, such that for all input sizes that are bigger than or equal to that E dollars,

the running time 5N is always less than or equals a C time as D D dollars.

Whoa, that's a mouthful.

What does that actually mean in a way that normal people can understand?

Haha, fair enough.

Think of it this way.

5N is Big O of D chaw.

Basically means that as our problem size, that dollar gets absolutely huge.

Like monstrously huge.

Yeah.

The time our algorithm takes, that A then won't grow any faster than some multiple of G time.

So G time is like a ceiling.

It's a guarantee that things won't get worse than this.

So it's like a worst case scenario kind of thing.

Exactly.

In the worst case, this is roughly how much time it'll take as the problem gets really big.

Okay, that makes sense.

Now, what about Big Omega notation?

Is that kind of the opposite?

You got it.

Big Omega, written as Omega, gives us a lower bound.

A lower bound.

We say 5N is Big Omega of Cuba dollars, if there's some positive constants.

Again, let's call them 6 bands.

So that for all dollar greater than or equal to that Nick damn doll, is always greater than or equal to two 6 damn dollars.

So basically, no matter how big the problem gets, it's never going to be faster than this.

It's like a best case scenario in a way, right?

You could think of it that way.

It tells us the algorithm will take at least this much time as the input size grows.

Okay, so Big Bow is the ceiling, Big Omega is the floor.

Now we've got Big Theta, which sounds like it's right in between.

Yeah, you're right on track.

Big Theta or Theta is all about a tight bound.

A tight bound.

We say Phi Theta is Big Theta of DM, if we can find some positive constants.

And we need three this time.

Let's call them B dollars, and D dollars.

Okay, getting a little complex here.

So that for all greater than or equal to two C dollars is less than or equal to FN, which is less than or equal to two times times DMN.

So basically, our running time is sandwiched between these two multiples of each.

Exactly.

It's trapped.

And that means Phi rho BN grows at basically the same rate as GNN,

not faster, not slower.

It's a very strong statement about the growth rate.

And this is the gold standard, right?

Like, if we can say an algorithm's running time is Big Theta of something, that's the most informative thing we can have.

You're absolutely right.

It's the most precise description we can get.

And here's a cool connection.

A function Fogan is Big Theta of GN, if and only if it's both Big O of Dionega and Big Omega of GNN.

So if it's bounded above and below by the same rate, then that's its growth rate.

Yeah,

totally.

So when we're trying to analyze the running time of algorithms,

are we always aiming for this Big Theta notation?

Ideally, yes.

When we do this, though, we usually focus on the dominant term in the running time and ignore the smaller terms and constants.

Why is that?

Because as DNN gets really, really big, those less significant terms just don't matter as much.

They get dwarfed by the term that grows the fastest.

Okay, so it's like, if we figure out an algorithm takes, let's say, $3 .10 plus $5 plus $10 operations for a huge dollar, that $10 to part is what really matters.

Precisely.

We'd say it's Big Theta of $10.

Got it.

Now, can we see this in action, like, with real algorithms?

Let's take insertion sort, for example.

In the worst case scenario where the input is totally backwards, it has to compare and maybe shift each element with every other element.

Oof, that sounds inefficient.

Yeah, and this leads to a running time that's basically proportional to $10.

So we'd say its worst case running time is Big Theta of $10.

Okay, so the initial order of the data really matters for insertion sort.

Yeah, it does.

But in the best case, where the input's already sorted perfectly, it only needs to do a minimal amount of work, like, just check each element once.

So then it's much faster.

In that case, the best case running time is Big Theta of $10.

Wow, what a difference.

What about something like merge sort?

Ah, merge sort.

It's a real workhorse.

I've heard it's more efficient in general.

You've heard right.

It uses this divide -and -conquer strategy.

It breaks the problem down into smaller pieces, solves those, and then merges the results back together.

Clever.

And the beauty of merge sort is that it's pretty consistent.

No matter what the input looks like, it has a running time of Big Beta of 1 old GN dollar.

1 old GN dollar.

Yeah, no loss log dollar.

That log null factor comes from how many times it divides the array, and the dollar comes from the work of merging everything back together.

Okay, so consistency is a good thing, especially when you can't always guarantee your data will be nice and organized.

Now, you mentioned earlier that we have to be careful about how we use this notation.

Can you elaborate on that?

What would be considered bad form when using Big Omega and Big Theta?

Yeah, it's all about being precise.

When we're using Big Theta, for example, it's super important to specify whether we're talking about the worst case, the best case, or maybe even the average case running time.

Right, right.

Context matters.

It does.

Like, if we just say insertion sort's running time is Big Theta of 2 dollars.

There's 2 to 1.

Without saying anything else, that's not quite right, because that only holds true for the worst case.

But if we want to give a general upper bound that applies to every single input, then it would be accurate to say insertion sort's running time is Big O of 2 dollars C.

Because it'll never be worse than that.

Exactly.

So you see, Big O can be a bit more general.

It gives us a safe upper limit no matter what.

Big Theta, on the other hand, that's a much more specific statement.

So it's all about choosing the right tool for the job.

Now, I got to ask.

I've always been a little confused about how this notation works in equations and inequalities.

It's weird to see something like Big O n.

It's like, how can a function equal Big O of another function?

Yeah, I know what you mean.

It can look a little strange.

But the thing is, when we see something like that, that equal sign isn't really an equal sign in the traditional sense.

It's not.

Nope.

What it really means is that Kig O belongs to the set of all functions that are Big O of Big O's.

So it's more like set membership.

Hmm.

So it's like Phi SN is a member of the Big O of GN club.

Uh -huh.

Yeah, something like that.

And when you see this notation inside a bigger formula.

Let's say we have something like 2n and 2 plus o n, that Big O of null part, that just represents some function that grows no faster than no r.

We don't know exactly what it is, but we know it's bounded by no r.

Okay, so it's like a placeholder for some unknown function that behaves in a certain way.

Exactly.

And if you see Big O on the left -hand side of an equation, it means that for any function that fits the description on the left, there's some function on the right that makes the equation true.

Still a little abstract, but I'm starting to get it.

Now, what about these proper abuses of notation that the chapter talks about?

What's that all about?

Oh, yes.

That sounds kind of funny, right?

Proper abuse.

But basically, it's just referring to some common conventions that people in the field use.

So shortcuts.

Exactly.

Like we always use the equal sign instead of the set membership symbol.

It's just easier.

Everyone knows what we mean.

Right.

Right.

Like a shorthand.

Yeah.

And usually we're always interested in what happens as dollar gets really, really big.

So we don't always write that out explicitly.

Okay.

That makes sense.

What about when you see Big O of one, like o -o -do?

What's that all about?

Oh, that's a good one.

Big O of one means that the running time is constant.

Constant.

Yeah.

Doesn't change no matter how big the input gets.

Sometimes you might see it used to describe the time it takes for something to happen if the input is really small, like the first few steps take over dollar, talk allers, for some thousand three.

What that means is that for those small input sizes, the time is limited by some constant.

We don't necessarily know what that constant is, but it's fixed.

Okay.

So these proper abuses are basically just ways to make the notation more usable in practice.

We're all on the same page.

So we can use these shortcuts without getting confused.

Exactly.

Now let's talk about the less famous siblings of Big O and Big Omega.

Little o and Little Omega.

Oh, yeah.

Those are a little more mysterious.

How did they differ from their big brothers and sisters?

So little o, written as a nolo, is also an echo bound, but it's not asymptotically tight.

Not tight.

What does that mean?

It means that phi phi fan grows strictly slower than your enimondal.

Like no matter how much you scale down dollars, eventually a phi fan will become smaller than that scaled down versions their deal gets large.

I see.

So it's a stronger statement than Big O.

Yeah, you could say that.

Like for example, nolo is as little o of two, two, two because nolo gets huge, nolo becomes tiny compared to two twos, right?

But two nolo is not little o of two, two because no matter what constant you pick, two tube is never going to be strictly smaller than itself for large dollars.

Okay.

So it really captures that strictly slower idea.

Now, what about Little Omega?

Little Omega, written as the mega, is the opposite.

It's a lower bound that's not asymptotically tight.

So it means phi fan grows strictly faster than a jigsaw.

Exactly.

No matter how much you scale up dp, eventually phi fan will be bigger.

Okay.

So we've got upper bounds, lower bounds, tight bounds.

And the little evasions tell us about strict inequalities.

It reminds me of how we compare normal numbers, you know, greater than, less than, equal to.

Yeah, it's a good analogy.

Big O is like less than or equal to.

Big Omega is like greater than or equal to.

And Big Theta is like equal to.

And little o is like strictly less than and little omega is like strictly greater than.

Exactly.

But, and this is super important with numbers, one of those three things must always be true.

Like either a is less than Beiler or it equals Beiler's or is greater than Beiler's.

But that's not always the case with asymptotic notation.

Wait, really?

Yeah.

There are functions where you can't say one grows faster than the other or that they grow at the same rate.

They might kind of weave in and out of each other.

Wow.

That's interesting.

So sometimes you just can't compare them directly.

Now the chapter also takes us through a bunch of standard math notations and common functions.

It's like a toolbox for analyzing algorithms.

It's like our math survival kit.

Exactly.

So first up, we have monotonicity, increasing and decreasing functions, right?

Yeah.

A function, bull enna, is increasing if whenever in dollars is less than or equal to an hour, then bull enna is less than or equal to enna.

And strictly increasing if bull Ehlers is less than n always means bull Ehlers is less than bull enna.

Okay.

And decreasing is the opposite.

Exactly.

If Mauler less than or equal to Ehler means ball Emma's is greater than or equal to Ehlers, then it's decreasing and strictly decreasing if it's always greater than.

Got it.

Now what about these floor and ceiling functions?

Those are important.

The floor function of a number written as bull XON just gives you the biggest integer that's less than or equal to 6n.

So it rounds down.

Exactly.

And the ceiling function, a toll X feel, gives you the smallest integer that's greater than or equal to 6n.

So it rounds up.

You got it.

These are useful because we're often dealing with whole numbers, you know, like the number of steps in an algorithm.

Right, right.

And what about modular arithmetic?

When does that come into play?

Modular arithmetic is all about remainders.

When you divide one number by another, what's left over?

That's the remainder.

Okay.

So modular arithmetic, written as a PMOD, is just the remainder when ALE is divided by another.

And two numbers are equivalent modular dollar if they have the same remainder.

So like 10 and 25 are equivalent modular five because they both have a remainder of a zero when you divide them by five.

Exactly.

Modular arithmetic pops up all over computer science, especially in things like hashing and cryptography.

Cool.

Now let's move on to polynomials.

Those appear everywhere when analyzing running times.

Yep.

A polynomial is just a function that looks like PPN is ULLAR plus A1n plus A2n2 plus P plus 8AD.

So a bunch of terms with increasing powers of non.

Exactly.

And the degree of the polynomial is just the highest power of non -dollars that appears.

Okay.

Now when it comes to asymptotic analysis, a key thing to remember is that the growth of a polynomial is determined entirely by its highest degree term.

So all those other terms, the smaller powers of non -dollars, they don't matter as much.

Not when DIMED gets really big.

The highest degree term takes over completely.

That's why when we analyze algorithms with polynomial running times, we usually just focus on that dominant term.

Got it.

And then we have exponential functions, which we know can grow super fast.

Oh, yeah.

Exponential functions.

They're like the rockets of the function world.

They take off.

Uh -huh.

I like that.

So what's the deal with them?

Well, they have the form one -hour, where it's a constant, usually bigger than one.

Okay.

And the key thing here is that they grow much faster than any polynomial, no matter how high the degree of that polynomial.

That's why if an algorithm has an exponential running time, it's usually considered impractical for large inputs.

It'll just take way too long.

And at the opposite end of the spectrum, we have logarithms, the slope oaks.

The snails of the function world.

Uh -huh.

So what's the deal with them?

They grow really, really slowly.

And they're the inverse of exponentiation.

Like, if Y is OCDL, then the logarithm base of power is DELIAS.

In computer science, we usually use base two logarithms, written as Gull and Day.

And a key thing to remember is that logarithms grow much slower than polynomials, like way slower.

Got it.

So polynomials grow faster than logarithms, and exponentials grow faster than both.

Now, what about factorials?

Those are famous for their explosive growth.

Oh, yeah.

Factorials are like the fireworks of the math world.

They just explode.

Uh -huh.

All right.

So what are they all about?

The factorial of a number, no dollar, written as not in a day, is just the product of all the positive integers up to no.

So like, $5 is $5, 4, 3, 2, and around, which is 120.

And $0 is defined as 1, by the way.

Okay.

Now, factorials can get really big, really fast.

So we often use something called Stirling's approximation to estimate them for large values of, it's a bit of a complicated formula, but it basically says that $0 is approximately equal to the square root of $2 enters,

high end times null.

So it's a way to get a handle on how quickly they grow.

Exactly.

And they grow much faster than exponentials.

Wow, that's fast.

It is.

And then we have something called functional iteration, which sounds fancy, but is actually pretty simple.

Okay, I'm listening.

It's just applying a function to an input multiple times.

So like, if we have a function, thumbtacks, $2, $1, then $5 down there means we apply synapse.

So it'd be $5, which is $5, which is $4 down.

Okay.

So it's like a chain reaction.

Exactly.

You just keep applying the function over and over again.

And this comes up in some algorithms where you repeat a certain step a bunch of times.

Now, what about this iterated logarithm function?

That sounds like it could be intense.

It sounds scarier than it is.

The iterated logarithm written as ligand f is just the number of times you have to take the logarithm of non -old dollar before you get a number that's less than or equal to one.

So how many times you have to hit the log button on your calculator before you get a small number?

Yeah, exactly.

And the cool thing is that this function grows incredibly slowly.

Like for any number you'll ever actually encounter in real life, the iterated logarithm is probably going to be five or less.

It's almost like a constant.

Wow, that's slow.

It is.

And finally, we have the Fibonacci numbers, which are kind of like the celebrities of the math world.

They pop up everywhere.

Okay.

Tell me about them.

The Fibonacci sequence starts with zero and one, and then every number after that is the sum of the two previous numbers.

So it goes zero, one, one, two, three, five, eight, 13, and so on.

Okay.

I've seen that pattern before.

It's everywhere.

And there's actually a formula for the Fibonacci number that involves something called the golden ratio.

It's a bit complicated, but basically the Fibonacci numbers grow exponentially.

So they get big quickly.

Now,

the chapter also includes a handy glossary of terms that covers all the basics like algorithm and running time, as well as some of the more technical terms we've talked about today.

It's like a little dictionary for algorithm analysis.

Exactly.

So it's there for reference just in case you need to refresh your memory on any of these concepts.

It's a good reminder that we need to be precise when talking about these things.

We need to use the right terminology and understand the nuances of all these different concepts.

I think we've covered it all right.

Asymptotic efficiency, big O, big omega, big theta, little O, little omega, all the good stuff.

Yeah.

We've hit all the major points and we've seen how this notation allows us to talk about algorithm performance in a really precise way.

It helps us compare different algorithms and understand how they scale as the input size grows.

Exactly.

It's not just about theory.

It's about understanding the tools that we use to build the technology that we use every single day.

Right.

And it shows how seemingly abstract math concepts can have a huge impact on the real world.

And that's a wrap.

Thanks for joining us on this deep dive.

Hopefully you've learned a little something about the fascinating world of algorithm analysis.

It's been a pleasure.

And hey, here's something to think about.

Next time you're using your favorite app or website, consider the algorithms working behind the scenes.

How are they handling all that data?

How efficient are they?

And how might a little bit of optimization make a huge difference in your experience?

Food for thought.

Absolutely.

It's everywhere if you know what to look for.

Until next time.