Introduction

How do you study the asymptotic efficiency of algorithms?
You study the asymptotic efficiency of algorithms by looking at input sizes large enough to make only the order of growth of the running time relevant.

Usually, an algorithm that is asymptotically more ... will be the ... choice for all but very ... inputs.
Usually, an algorithm that is asymptotically more efficient will be the best choice for all but very small inputs.

Asymptotic Notation: informal introduction

What does Big-O notation say about the growth of a function?
Big-O notation says that the growth of a function will not be faster than a certain rate based on the highest order term.

If a function is , what is it also?
If a function is , it is also .

What does Omega notation () say about the growth of a function?
Omega notation () says that the growth of a function will be as fast as a certain rate based on the highest order term.

If a function is , what is it also?
If a function is , it is also and .

What does Theta notation () say about the growth of a function?
Theta notation () says that the growth of a function will be precisely at a certain rate based on the highest order term.

If a function is , what is it also?
If a function is , it is nothing else.

Asymptotic Notation: formal definition

...

What is the alternative definition of Big-O notation using a limit?
The alternative definition of Big-O notation using a limit is:
...

What is the alternative definition of Omega notation () using a limit?
The alternative definition of Omega notation () using a limit is:

...

What is the alternative definition of Theta notation () using a limit?
The alternative definition of Theta notation () using a limit is:

...

How can you determine the Omega notation () of a function without using a definition?
You can determine the Omega notation () of a function without using a definition by throwing away lower-order terms and ignoring the leading coefficient of the highest order term.

Todo

There's a section where he talks about how Omega notation () gives you a more exact running time of an algorithm. I asked Gemini about that section and it thought it wasn't correct. I will omit it for now until I can verify its accuracy.

What is the theorem for Theta notation ()?
The theorem for Theta notation () is that for any two functions and , .