Check out this site on asymptotic notation. Big O is just an upper bound for the runtime. Expressing the average case with big O is equally valid as expressing the worst case with it.

I’ll reply a bit later with the other questions when I get a chance to look at it properly.

Silly me. O(n log n) is off course true JUST for the balanced tree.

I apologize: I had been looking at other resources for potential solutions, when I got stuck, but @tagrockstar79958 solutions’ appears to use two objects as I desired.

I appreciate the answer, but does this mean you believe my solution runs in O(n)? Or does it mean, you thought I said O(2n)? Maybe, I should have said: O(n^2) or O(n)?

Sorry, I’m not entirely sure what the time complexity actually is. My comment only referred to constants being excluded. If there is a nested loop, then it is O(2^n), but if it is two consecutive loops, it is O(n).

Going to defer to a member better qualified in this area, @alexc.