How fast can you find the maximum? (A surprising result!)

by greenturtle3141, Nov 13, 2021, 5:52 AM

Reading Difficulty: 3-4/5
Prerequisites: Definitely need to know what a graph (...with vertices and edges) is. Good to be familiar with linearity of expectation.

Professor Tkocz was the substitute professor for combinatorics class today... and it was wild! Here's what I learned.

Part 1: Introduction

I hand you a list of $100$ numbers. How fast can you find the largest one?

One way to find the largest is pretty simple: Go through the numbers one-by-one, and keep track of the biggest one you've seen before. You're done once you reach the end of the list. Because of the linear nature of this algorithm this, is an $O(n)$ algorithm. That is, this algorithm needs you to compute at most $an+b$ comparisons for some $a$ and $b$ .

# I HAVE NO IDEA WHY THIS CODE IS SUCH A BAD COLOR AND IM SORRY FOR MY SINS
def findMax(nums):
    currMax = nums[0]
    for num in nums:
        if num > currMax:    # This gets called at most n+1 times, so findMax is O(n)
            currMax = num

    return currMax

It's evident that we can't do better than $O(n)$ comparisons (Exercise: Why?), so this is boringly optimal. Post is done yay.

What if I gave you a team of $100$ people (including you) to find the maximum of a $100$ -element list? How fast can you do it then?

You guys all get to work in parallel. Everyone can think at the same time and share information infinitely fast... Can you come up with a really fast strategy to find the maximum?

In general, suppose I give an $n$ -element list of numbers to a team of $n$ people. How fast can they find the maximum element? Mathematicians have suspected that with a clever enough general algorithm, this can be done in constant time, i.e. $O(1)$ . We just couldn't find one. Is it possible?

Eventually, we got our answer.

THEOREM: No matter what algorithm you use, $n$ parallel processors cannot find the maximum of an $n$ -element list in constant time. In particular, any maximum-finding algorithm has worst-case time complexity at least $\Omega(\log \log n)$ .

Why Big-Omega and not Big-O?

To be more precise: An algorithm will consist of several rounds, where in each round we make $n$ comparisons at once (which pairs of numbers we decide to compare in a round may be decided based on the results of the previous round). For example, if $n=4$ and my list is $[x_1,x_2,x_3,x_4]$ , an algorithm could do this:

Round 1: Compare the pairs $(x_1,x_2),(x_2,x_3),(x_3,x_4),(x_1,x_3)$ .
Result: $x_1<x_2$ , $x_2 > x_3$ , $x_3 < x_4$ , and $x_1 > x_3$ . (Note that this is not enough to find the max! Could be $x_2$ or $x_4$ .)
Round 2: Compare the pairs $(x_2,x_4), \cdots$ .
Result: $x_2 > x_4$ , etc.
Conclusion: $x_2$ is the maximum.

Modelling an "algorithm" in this way, the Theorem states that the number of rounds is at least $\Omega(\log \log n)$ in the worse case, no matter how clever you are.

Let's prove this!

Part 2: Turán's Theorem

We need to talk about some graph theory here. The graphs we'll consider are simple ones: They're finite, no loops, have undirected edges, no multi-edges... they're all nice.

Definition: Let $G = (V,E)$ be a graph. A subset $S \subseteq V$ of the vertices is an independent set if no two vertices in $S$ are connected by an edge.

Pretty intuitive definition. Moving on:

Definition: The independence number of a graph $G$ , denoted by $\alpha(G)$ , is the maximum size of an independent set.

For example (verify these!):

$\alpha(K_5)=1$ , where $K_5$ is the complete graph on $5$ vertices.
$\alpha(C) = 4$ , where $C$ is the graph whose vertices and edges correspond to those of a cube.
$\alpha(K(m,n)) = \max(m,n)$ where $K(m,n)$ is the complete bipartite graph on two vertex sets of size $m$ and $n$ .

The question is: How big must $\alpha(G)$ be? That is, if there are $n$ vertices and $m$ edges, can we guarantee that there must exist an independent set whose size is at least <some formula in terms of $m$ and $n$ >? Turán's Theorem answers this.

Theorem (Turán): $\alpha(G) \geq \frac{n^2}{2m+n}$

Proof. The idea is to use the probabilistic method. To wit, consider a random labelling $\pi:V \to [n]$ of $V$ with the integers $1,2,\cdots,n$ . Using $\pi$ , we may generate an independent set $I(\pi)$ as follows:
$I(\pi) := \{v \in V : \pi(v) < \pi(w)\,\forall w \in N(v)\}$ Here, $N(v)$ is the set of neighbors of $v$ . To describe $I(\pi)$ in other words, each $v \in I(\pi)$ is such that over $v$ and all its neighbors, $v$ has the least label.

Note that indeed $I(\pi)$ forms an independent set (Proof). Now, what is its expected size when $\pi$ is chosen uniformly at random over all labelings? To compute this, we write $|I(\pi)|$ as a sum of indicator random variables:
$|I(\pi)| = \sum_{v \in V} 1_{I(\pi)}$ Taking the expectation and applying linearity of expectation, we get:
$\mathbb{E}|I(\pi)| = \sum_{v \in V} \mathbb{E}1_{I(\pi)} = \sum_{v \in V} \mathbb{P}(v \in I(\pi))$ By a simple counting argument, $\mathbb{P}(v \in I(\pi)) = \frac{1}{1+\deg v}$ . So we have:
$\mathbb{E}|I(\pi)| = \sum_{v \in V} \frac{1}{1+\deg v}$ We're almost there. How can we wrestle this into the desired lower bound? The punchline is to apply the AM-HM inequality on the sum! Recall by the Handshake Lemma that:
$\sum_{v \in V} \deg v = 2m$ So using $\text{AM} \geq \text{HM}$ :
$1+\frac{2m}{n} = \frac1n\sum_{v \in V} (1+\deg v) \geq \frac{n}{\sum_{v \in V} \frac{1}{1+\deg V}}$ This rearranges to $\sum_{v \in V} \frac{1}{1+\deg v} \geq \frac{n}{1+\frac{2m}{n}} = \frac{n^2}{n+2m}$ . By the probabilistic method, we deduce that there exists an independent set of size at least $\frac{n^2}{n+2m}$ , hence it certainly follows that $\alpha(G) \geq \frac{n^2}{n+2m}$ . $\square$

Apparently this bound is actually pretty tight, and there are some nice corollaries you can deduce from this. But I won't discuss this, for we have bigger fish to fry!

Part 3: The Main Event

Theorem: Any algorithm for finding the maximum of an $n$ -element list, using $n$ parallel processors, must have worst-case time complexity at least $\Omega(\log \log n)$ (provided that a comparison is an $\Omega(1)$ operation).

Proof. Considering the "rounds" structure described in the introduction, note that each round can only really tell you so much about which numbers is the maximum. In fact, a round of comparisons may even leave you with a subset of vertices that you have no information on, in the sense that you don't know the order of any two vertices in the subset. Hmm... doesn't that smell like "independent sets"? Controlling the size of such a subset is the key machinery in this proof.

This idea is captured by the following Lemma:

Lemma: Let $C(n,m)$ be the worst-case minimum number of rounds needed to determine the largest element of an $n$ -element list using $m$ parallel processors. Then:
$C(n,m) \geq 1 + C\left(\left\lceil \frac{n^2}{2m+n} \right\rceil,m\right)$
Proof. Let the list be $x_1,\cdots,x_n$ . Suppose an algorithm decides to compare $(x_{i_1},x_{j_1}),(x_{i_2},x_{j_2}),\cdots, (x_{i_m},x_{j_m})$ in the first round. Now construct a graph $G$ whose vertices are $x_1,\cdots,x_n$ and with $m$ edges $\{x_{i_1},x_{j_1}\},\{x_{i_2},x_{j_2}\},\cdots, \{x_{i_m},x_{j_m}\}$ . By Turán, $\alpha(G) \geq \frac{n^2}{2m+n}$ . Hence there exists an independent set $I$ with size at least $\left\lceil\frac{n^2}{2m+n}\right\rceil$ . Now we argue:

Since $I$ is independent, this means that we have no information on how any two elements in $I$ compare.
In the worst case scenario, the maximum will lie in $I$ .
Hence, in the worst case, finding the maximum of $G$ is at least as hard as finding the maximum of $I$ .
In other words, the number of more rounds we need to find the maximum of $G$ , in the worse case, is at least the number of rounds we'd need to find the maximum of just those elements in $I$ .
As $|I| = \left\lceil\frac{n^2}{2m+n}\right\rceil$ , this number is given by $C\left(\left\lceil \frac{n^2}{2m+n} \right\rceil,m\right)$ .

Since we spent a first round, we must add $1$ , giving the desired lower bound $C(n,m) \geq 1 + C\left(\left\lceil \frac{n^2}{2m+n} \right\rceil,m\right)$ . $\square$

Going back to the main proof, the rest is just some algebra and hand-waving. By handwaving, I mean that I will now drop the ceiling function and leave it to the reader to make this more rigorous, otherwise this would be unpleasant to read.

The number we are bounding is $C(n,n)$ . Let's just keep plugging this into the Lemma.
$\begin{align*} C(n,n) &\geq 1 + C\left(\frac{n^2}{2n+n},n\right) = 1 + C\left(\frac{n}{3},n\right) \\ &\geq 2 + C\left(\frac{(n/3)^2}{2n+n/3},n\right) = 2 + C\left(\frac{n}{3^2\cdot 2 + 3},n\right) \geq 2 + C\left(\frac{n}{3^3},n\right) \\ &\geq 3 + C\left(\frac{(n/3^3)^2}{2n+n/3^3},n\right) = 3 + C\left(\frac{n}{3^6 \cdot 2 + 3^3},n\right) \geq 3 + C\left(\frac{n}{3^7},n\right) \\ &\geq 4 + C\left(\frac{(n/3^7)^2}{2n+n/3^7},n\right) = 4 + C\left(\frac{n}{3^{14} \cdot 2 + 3^7},n\right) \geq 4 + C\left(\frac{n}{3^{15}},n\right) \\ &\geq \cdots \end{align*}$
In general (by induction), we have that $C(n,n) \geq k + C\left(\frac{n}{3^{2^k-1}},n\right)$ for all $k$ ... kinda. Once the number of vertices left, $\frac{n}{3^{2^k-1}}$ is $1$ or less, we can't go further. Hence, $C(n,n) \geq k$ where $k$ is the least integer for which $\frac{n}{3^{2^k-1}} \leq 1$ . Manipulating this:
$\frac{n}{3^{2^k-1}} \leq 1$ $n \leq 3^{2^k-1}$ $2^k-1 \geq \log_3 n$ $k \geq \log_2(1 + \log_3 n) = \Omega(\log \log n)$ Q.E.D. $\square$

This post has been edited 3 times. Last edited by greenturtle3141, Nov 13, 2021, 6:00 AM

combinatorics

Fun Theorems

Comment

1 Comment

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ah yes the sum 1/(deg v + 1) result is fun

by depsilon0, Nov 19, 2021, 9:56 PM

Report

Submit

Can you give some thought to dropping a guide to STS? Just like how you presented your research (in your paper), what your essays were about, etc. Also cool blog!
by Shreyasharma, Mar 13, 2025, 7:03 PM
this is so good
by purpledonutdragon, Mar 4, 2025, 2:05 PM
orz usamts grader
by Lhaj3, Jan 23, 2025, 7:43 PM
Entertaining blog
by eduD_looC, Dec 31, 2024, 8:57 PM
wow really cool stuff
by kingu, Dec 4, 2024, 1:02 AM
Although I had a decent college essay, this isn't really my specialty so I don't really have anything useful to say that isn't already available online.
by greenturtle3141, Nov 3, 2024, 7:25 PM
Could you also make a blog post about college essay writing :skull:
by Shreyasharma, Nov 2, 2024, 9:04 PM
what gold
by peace09, Oct 15, 2024, 3:39 PM
oh lmao, i was confused because of the title initially. thanks! great read
by OlympusHero, Jul 20, 2024, 5:00 AM
It should be under August 2023
by greenturtle3141, Jul 11, 2024, 11:44 PM
does this blog still have the post about your math journey? for some reason i can't find it
by OlympusHero, Jul 10, 2024, 5:41 PM
imagine not tortoise math

no but seriously really interesting blog
by fruitmonster97, Apr 2, 2024, 12:39 AM
W blog man
by s12d34, Jan 24, 2024, 11:37 PM
very nice blog greenturtle it is very descriptive and fascinating to pay attention to
by StarLex1, Jan 3, 2024, 3:12 PM
orz blog
by ryanbear, Dec 6, 2023, 9:23 PM
Hi! Cool blog!
by mahaler, Nov 14, 2021, 3:08 PM
fascinating...
by pi271828, Nov 14, 2021, 12:00 AM
I believe that indeed, turtles come in all sorts of different colors. Even real ones! Some googling shows that indeed, red turtles seem to exist, though they're not that red.
by greenturtle3141, Nov 13, 2021, 9:21 PM
hello

since you have turtle knowledge, does your species of green turtles have a brethren that possess a color of red? what about blue? what about tawny mauve?
by pi271828, Nov 13, 2021, 9:18 PM
Nice Blog!
by Jwenslawski, Nov 13, 2021, 6:22 PM
Looking especially forward to how you improved on your AMC/AIME/USAMO so quickly
by StopSine, Nov 11, 2021, 2:01 AM
thanks the_turtle
by pog, Nov 10, 2021, 1:09 PM
another turtle blog?
by The_Turtle, Nov 9, 2021, 2:23 AM
Looking forward to future posts!
by Arr0w, Nov 2, 2021, 6:15 PM
just copy and paste every single one of your msm posts and thisll become the best blog ever hahahaha
by peace09, Nov 1, 2021, 9:33 PM
hello!
by tigerzhang, Nov 1, 2021, 9:09 PM
3rd shout! Yay greenturtle blog!
by violin21, Oct 25, 2021, 1:04 AM
hello $\text{[math]}$ $\text{[math]}$
by v4913, Oct 24, 2021, 5:33 PM
first shout
by mathlearner2357, Oct 24, 2021, 5:12 AM

67 shouts

Turtle Math

How fast can you find the maximum? (A surprising result!)

by greenturtle3141, Nov 13, 2021, 5:52 AM

1 Comment