OK.

Again, you're all recorded, just as you know.

Good.

I hope everybody is well and OK today.

Let's briefly recap what we did last time, because this is really, really important that

you have a sort of intuition about program runtimes and complexity.

So remember, we want to evaluate the program's efficiency when the input is very big towards

infinity, so in the limit.

And we basically want to characterize a program's runtime as the input grows.

Yeah, so we usually neglect the constants and stuff like this.

Constants can become important, as we'll see later, but for now, we just neglect them and

want to basically just put a very tight upper bound on the program complexity and the growth.

We're interested in the delta and the growth, so how quickly does a program grow with the

size of the input?

We don't need to be very exact, so we're usually talking in terms of order, magnitude, something

like is it linear or prophetic, polynomial, exponential, any of these.

But we're not so much interested in order constant factors, so to be very, very exact

on the growth.

So the largest factors determine the runtime.

We've seen last time usually four loops, nested loops, things like that.

The one thing I really want you to remember is the laws of addition and multiplication.

When do you do what?

So things subsequently add up and things nested within each other multiply.

Then what the rules are, what is actually left over?

So this is a very common exam question actually to simplify order of rotations and then get

the actual O notation out of any sort of estimate for a program.

Or basically, it could also be some pseudocode and you're asked to estimate the complexity

of the program.

All of these are possible questions.

So these are probably the ones you need to keep in mind.

O of one denotes constant runtime, so anything that's just assigning something or whatever

is not very interesting usually, but all O ones are anything that's constant.

Log N, logarithmic runtime, do you remember how to spot logarithmic runtimes?

When does this usually happen?

Do you remember that?

It's a for loop over all elements in an array logarithmic.

Yes, no?

Who's for yes?

Who's for no?

Nobody woken up yet.

Everybody's shy.

Okay, every element of an array is O of N, right?

Grows linearly with the number of elements in the array.

So what could be log N?

Log N is faster than N, right?

Remember this.

Well, what would happen?

I cannot pass over every element in an array in a log N algorithm.

What is the giveaway for log N's usually?

Sorry?