The problem with links is that you don't know where they are going to take you. When I have such a nice piece of text to read I don't want to click and potentially land in a completely different site, have to click "back" and all that distracting stuff. That's probably why your link didn't "register" with me. In your case in turns out the link nicely expands in place, so that's pretty cool. I'd still just inline that little explanation on Big O, since you keep referring to it in the rest of the text. It's more than a mere footnote.
Now this is all my own experience, and others may disagree, so don't necessarily go changing things just on my account!