[Strilanc]

I (the author) actually did lose a lot of time trying to prove those weren't the same bound! Eventually I found a variable assignment that made it obvious:

    let w = n/log(n)
    let h = n

    (Note: I use ↑ and ↓ as binary operators for max and min.)
    (Note: @= means asymptotically equal. Analogous for @<.)
     
    'switching'
    @= (w ↑ h) ↓ ((w ↓ h) log(w ↑ h))
    @= (n/log(n) ↑ n) ↓ ((n/log(n) ↓ n) log(n/log(n) ↑ n))
    @= n ↓ (n/log(n) log(n))
    @= n

    'lower'    
    @= ((w ↓ h) log((w ↑ h)/(w ↓ h))
    @= n/log(n) log(n/(n/log(n))
    @= n log(log(n)) / log(n)
    @< n

[rwitts]

Very nice! I'm glad that you worried about this and I have to admit that your asymptotic example is nicer than mine.