Fa17 CS 61B Discussion 6

Announcements

• Project 1 is due 10/13!
• Start early!

Asymptotics

Asymptotics is the whole reason for 61B

• If we did not care about efficiency of our code, why use different data structures at all?
• Just use arrays and be done with it!

Key Idea

• Asymptotics describe how a function grows as input size grows.

Example

• Consider the following example.

​

​

​

​

Example

• As the size of our array grows, how many more print statements do we execute?
• Thus, what is our runtime?

Example

• As the size of our array grows, how many more print statements do we execute?
• If we plot this, we will see a linear relationship between total print calls and array size.
• Our runtime is linear with respect to array size.

Another Example

Another Example

• If we increase array size by 1, the total number of calls to our print statement increases by 5.
• What is our runtime?

Another Example

• If we increase array size by 1, the total number of calls to our print statement increases by 5.
• But if we plot it, we still get a linear relationship!
• Therefore, the runtime is still linear.

Another Example

• Notice I did not say 5 x linear, just linear.
• This brings us to our next key idea...

Key Idea (The most key-est of them all)

• Asymptotics are approximations.
• To put it another way, we are not finding the runtime of a function.
• We are finding the family of runtimes that this function belongs to.

Example

• Say somehow, you’ve calculated that your Java function runs in f(n) = 100n⁴ + 0.2n³ + n² + log² n + 10500
• What is your runtime?

Example

• Our runtime is still Θ(n⁴).
• We’ll learn about the Θ notation later.
• We didn’t care about anything except the highest order term, and we dropped our constants.
• What we did was classify f(n) into the family containing all n⁴ functions.

Repeat after me...

• I PROMISE TO DROP MY CONSTANTS.
• Number one way to lose points on an asymptotic question.

Big-O, Theta, Omega

• Classifying functions into families is nice, but we want to find an upper limit or lower limit of our runtime.
• Same idea as before, using families.

Big-O, Theta, Omega

• Big-O: Upper bound.
• Big-Omega: Lower bound.
• Big-Theta: Tight bound (Upper bound == Lower bound)

Big-O

• If f(n) = n, g(n) = 100n², then we say f(n) is in O(g(n)).
• This says: f(n) is upper bounded by the family that g(n) is in.
• If I pick any function inside that family, it will be slower than f(n).
• Also called the worst-case bound.

Big-Ω

• If f(n) = 100n³, g(n) = n², then we say f(n) is in Ω(g(n)).
• This says: f(n) is lower bounded by the family that g(n) is in.
• If I pick any function inside that family, it will be faster than f(n).
• Also called the best-case bound.

Big-Θ

• If f(n) = 100n², g(n) = n², then we say f(n) is in Θ(g(n)).
• This says: f(n) is upper and lower bounded by the family that g(n) is in.
• Also called the tight bound.

Key Idea: Be Thick, Solid, and TIGHT

• If my function runs in f(n) = n time, then technically I could say that it is bounded by O(n¹⁰⁰).
• No credit on an exam!
• Also defeats the purpose of asymptotics.
• Be as tight as possible. Say Θ(n).

On to Discussion Q1, Q2

Common Paradigms

• 1 + 2 + 3 + 4 + … + n -> O(n²)
• Summation is equal to n(n + 1) / 2
• 1 + 2 + 4 + 8 + … + n -> O(n)
• To see this, take a look at the 8.
• Then, take a look at the numbers to the left of 8.
• Sums up to 7. Therefore we sum to 2n -> O(n)

Bits

Common Paradigms

• 1 + 2 + 3 + 4 + … + n -> O(n²)
• Summation is equal to n(n + 1) / 2
• 1 + 2 + 4 + 8 + … + n -> O(n)
• To see this, take a look at the 8.
• Then, take a look at the numbers to the left of 8.
• Sums up to 7. Therefore we sum to 2n -> O(n)