It seems like a dream now, but a few hours ago I sat through one of the worst exams of my college career! Data Structures and Algorithms (DSA) is one of those required computer science classes that makes or breaks CS majors… thank god I’m not a CS major (I’m computer engineering).
One of the problems was:
Given that T(n) = 3n – 1, prove that O(T(n)) = n2.
Any ideas? Yeah, I would have said that it was O(n), not O(n2)… so I BS’ed some stuff, totally making up everything I put down. Some of the stuff on trees was straightforward, but the proofs and mathematical theory parts weren’t trivial at all!