
タイトル：
BigTheta Examples  Intro to Algorithms

概説：

What the Big Theta allows us to do is basically write complicated functions

in a much simpler way.

We can take a function like ½n² and just think of it as Θ(n²).

And 8√n we can think of a just Θ(√n).

Our equation from before, 2n  2√n just becomes Θ(n).

It's just a linear function asymptotically.

A complicated expression like this where we have n⁴, which is the term that grows the fastest,

becomes Θ(n).

The ln nin fact, any base log n is Big Theta of any other base log n as long as it's a constant.

I like to think in terms of base 2 logs, because I'm a computer scientist.

That's what we do.

π² is something that doesn't grow with n, and it ends up being in the set Θ(1).

It's just another constant.

Just to beat this dead horse a little bit longer, let's use the definition of Big Theta

to show that this expression that we determine for the growth in edges in a grid

2n  2√nreally is just a linear function. It grows like Θ(n).

The game plan is that we need to find constant c₁ and c₂bigger than 0

and a threshold N₀ so that for all the n bigger than n₀, the function that we care about

is sandwiched between these two scalings.

Let's focus on this one first.

What c₂ can we plug in here so that we're guaranteed that this will be above this expression.

If we just copy this inequality down just flipping it around to make it a little easier to think about,

we want c₂ so that c₂n is bigger than this. Divide through by n

Now we need a c₂ that is bigger than 2 minus something that's actually growing.

Two should work for that.

If we set c₂ to 2, it will satisfy this inequality.

Let's just summarize all that

We can set c₂ = 2. What about c₁?

Well, let's take c₁ to be 1.

Intuitively, the idea being this function is growing like 2n minus something smaller than that.

So, n should be underneath that.

But let's just make show if c₁ is equal to 1, then we need n to be less than or equal

to this expression. For what values of n is that going to be true?

It's not true of all of them, but it's true for some of them.

We can add 2√n to both sides, subtract n from both sides, and we get that.

If we divide through by √n, we get 2 ≤ n/√n and divided by √n is actually √n.

So, we have 2 ≤ √n.

We square both sides. We have 4 ≤ n, orflipping that around the other way

if n ≥ 4, then this is true

That means we have to throw away the smaller values of n,

and we can do that very simply by setting n₀ to 4.

This only has to hold for n that are bigger than n₀.

That's what we've got there.

There we have it.

If we set the constants this way, n₀, c₁, and c₂, then what we find is

that for big enough n this more complicated expression is sandwiched between

two simple linear functions or to say it another way