Question
The quantum version of this algorithm requires destroying universes in which a list is unsorted. For 10 points each:
[10m] Name this purposefully awful sorting algorithm that either randomizes the order of a list until it is sorted or runs through the list of possible permutations.
ANSWER: bogosort [or quantum bogosort]
[10e] The deterministic worst-case scenario is having to check every single permutation, meaning bogosort is big-O of n times this function of n, which gives the number of permutations of n distinct objects.
ANSWER: factorial
[10h] The best-case scenario is having the first randomization be the sorted list, meaning that bogosort is big-[this letter] of n to account for the shuffling and checking process. This Greek letter represents the lower-bound time complexity of an algorithm.
ANSWER: omega [or big-omega]
<Lalit Maharjan , Science - Compsci>
Summary
| 2023 NASAT | 06/17/2023 | Y | 9 | 23.33 | 100% | 78% | 56% |
Data
| Asia B | Arkansas | 10 | 10 | 10 | 30 |
| Illinois Blue | California | 10 | 10 | 0 | 20 |
| Illinois White | Asia A | 10 | 10 | 0 | 20 |
| Ohio | Kentucky A | 0 | 10 | 0 | 10 |
| New Jersey B | Maryland Gold | 0 | 10 | 10 | 20 |
| Maryland Red | Missouri A | 10 | 10 | 10 | 30 |
| Missouri B | Virginia | 10 | 10 | 10 | 30 |
| Illinois Orange | New Jersey A | 10 | 10 | 0 | 20 |
| Pennyslvania | Kentucky B | 10 | 10 | 10 | 30 |