Find a nondecreasing function that’s O(n^2), Omega(n), and where those bounds can’t be improved

Essentially, you’re looking for a function that

1. has a tight quadratic upper bound,
2. has a tight linear lower bound, and
3. is nondecreasing.

Here’s one way to do this. Imagine drawing out the curves n and n². Now, draw your function f by first following the curve n² for some period of time, then drawing a horizontal line until you hit the curve n and tracing along that curve for a bit, then jump vertically to n² and follow that curve for a bit, repeating this process out to infinity. That is, we're looking for something like this:

The net effect of this is the following:

1. The n² curve is a tight asymptotic upper bound on f. The curve infinitely often takes on the value of n² and never exceeds n². That makes f(n) = O(n²) but not o(n²).

2. The n curve is a tight asymptotic lower bound on f. The curve infinitely often takes on the value of n but never drops below n. That makes f(n) = Ω(n) but not ω(n).

3. The function is nondecreasing.

The tricky part here is finding an exact formula for such a curve. We can do this using a recursive definition. The basic idea is the following:

1. Whenever f(n) = n (we’re hugging the bottom curve), we’ll set f(n+1) to (n+1)² so that we jump to the top curve.
2. Whenever f(n) > n, we’ll set f(n+1) = f(n). This corresponds to moving horizontally after hitting the top curve until we reach the bottom curve.

This gives us the following recursive definition:

Here’s the first few values taken on by this function:

0, 1, 4, 4, 4, 25, 25, 25, ..., 25, 676, 676, ...

This was a fun one to work through - hope this helps!