This lesson's interactive features are locked, please to keep using them

O(n^2) - Order “N Squared”

O(n^2) grows in complexity much more rapidly. That said, for small and medium input sizes, these algorithms can still be very useful.

A common reason an algorithm falls into O(n^2) is by using a nested loop, where the number of iterations of each loop is equal to the number of items in the input:

for person_one in persons:
    for person_two in persons:
        # every combination of people
        # will go on a date... twice!
        go_on_date(person_one, person_two)

Assignment

LockedIn needs search capabilities! For now, we'll build something slow (and frankly awful) so we can see an n^2 algorithm in practice.

Complete the does_name_exist function.

For each first name in first_names:
- For each last name in last_names:
  - If a first/last name combination (joined with a space) matches the full_name, it should return True.
If the loop finishes, it should return False.

Observe

When you run your completed code, notice how each successive call to does_name_exist takes quite a bit longer. Assuming the length of first_names and last_names is the same, each new name doesn't add n steps to the algorithm; the total number of steps grows quadratically with the size of the input, making the total work O(n^2).

If does_name_exist(10 names, 10 names) takes just 1 second to complete, then we can estimate:

does_name_exist(100 names, 100 names) = 100 seconds
does_name_exist(1000 names, 1000 names) = 10,000 seconds
does_name_exist(10000 names, 10000 names) = 1,000,000 seconds