Big Theta: Bounded From Both Sides, Keep Only the Dominant Term

What does bounding a function from both sides buy you, and why can Theta throw away every term but the dominant one?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Pinned between two copies of g

Theta asks two things of the same g: c0 times g(x) stays at or above f(x) from x0 on, and c1 times g(x) stays at or below f(x) from x1 on. Check each condition at every whole number from its own threshold up to and including 1000 (all() and range() may help); the video's f ( $3x^2 - 20x - 1$ ) and g ( $x^2$ ) are already defined. Define pinned(f, g, c0, x0, c1, x1) returning True only when both conditions hold.

Given code — runs before yours

# the video's cost function and its bounding function
def f(x):
    return 3 * x**2 - 20 * x - 1

def g(x):
    return x**2

def pinned(f, g, c0, x0, c1, x1):
    # Test the upper condition from x0 and the lower condition from x1, up to 1000.
    return ...  # your code here

def pinned(f, g, c0, x0, c1, x1):
    # Test the upper condition from x0 and the lower condition from x1, up to 1000.
    return ...  # your code here

Python runs in your browser

⌘/Ctrl + Enter runs

returns True or False

accepts the video's constants and thresholds, and a g that touches f

rejects the pair when either side breaks

checks each side from its own threshold

←Previous Big O: An Upper Bound That Only Has to Hold Past the Crossover Next Reading Theta Off the Loops: Two Laws and Six Complexity Classes →