Asymptotic Notation

Question 1

Big Theta Notation

When we use big-Θ notation, we’re saying that we have an asymptotically tight bound on the running time.

“Asymptotically” because it matters for only large values of n.

“Tight bound” because we’ve nailed the running time to within a c________ factor above and below.

Answer 1

constant

Question 2

Why n+1?

The t______ iteration at the end of a loop, etc

Answer 2

test

Question 3

Asymptotic Notation

Asymptotic Notation is used to describe the running time of an algorithm - how much time an algorithm takes with a given input, n.

There are three different notations: big O, big Theta (Θ), and big Omega (Ω).

Big-Θ is used when the running time is___________________________,
Big-O for the case_______________________
Big-Ω for the _________________________________

Answer 3

the same for all cases
the worst case
the best case

Question 4

Which Notation to use?

When you are considering a particular case, such as the worst case or the best case, you can speak in terms of e_______ bound Θ.

e.g.
Given an algorithm’s worst running time T(n)= 2n3 +n2 +n +1, best case running time T(n)= 100n2 +1000n +100

We can say that:

The algorithms’ worst-case running time is Θ(n3)
Its best-case running time is Θ(n2)

Answer 4

exact

Question 5

When instead, you speak about run time as a whole (combination of multiple cases),

you’ll say:

It can take no more time than O(…) (upper bound based on the worst case Θ(…))

Example

Its running time is O(n^3) = it can be anywhere from the lower bound
to this upper bound.

and no less time than Ω(…) (lower bound based on the best case Ω(…)).

Example

Its running time is Omega(n^2) = it can be no l_____ than that but it
could be anywhere up to the upper
bound.

Answer 5

less

Question 6

Comprehension Questions

1) What notation would we use to talk about a particular case
such as the worst case?

Answer 6

Theta (for exact bounds)

Question 7

Comprehension Questions

2) What notation can we use to talk about runtime as a whole?
I.e. where there may be variations.

Answer 7

We can use big O and Omega, because they will not be specific.
Big O will tell us what the runtime can’t be more than, but actually may be less than.

Big Omega will tell us what is can’t be lower than, but may actually be higher than.