Ah the beauty of big O, still remember it from a year ago. My teacher didn't like it that much, it was hard to get it wrong. Since big O is an upper bound you could have an algorithm that runs in linear time and say O(n^3) and still be right. I'm surprised you're covering big O at the graduate level, but I expect the algorithms you're dealing with must be very complex. In my Data Structures course we did mostly Θ(f(n)), and big O was merely used to defined Θ. Of course we covered simple data structures such as trees( AVL Trees, Red Black Trees, KD Trees..), Graph algorithms (Dijkstra, Bellman-Ford..), .. Although sometimes people use big O in terms of Θ since it's still right.