I'm a third-year Computer Science student in an online Data Structures class, and I'm running into a bit of a snag with a recent homework assignment. My professor marked my solution to a problem wrong, but I'm pretty sure my reasoning is sound. Here's the situation: the problem involves calculating the runtime of an algorithm that's O(n log n). For n=100, the algorithm supposedly takes 1/2 ms. I calculated that for n=500, it should take about 3.374 ms based on my workings. My professor, however, argued that my answer was incorrect and has been quite unresponsive after a few polite emails. I'm frustrated because I respect him and his teaching, but I feel like he's missed a mistake in his calculation. I've done a mathematical proof to support my answer, which I thought was a solid approach. Have I misunderstood something regarding this big O calculation?
1 Answer
It looks like your professor may have simplified the calculations incorrectly. Essentially, big-O notation is too general for precise calculations like this, and his method of dividing logs might not apply here. Instead of just canceling terms, you need to be careful about how logarithm properties work. Your approach seems to clarify that, so I'd say your calculations were on track!
I like how you broke this down! Logarithms can get tricky, so I'm glad you explained. I'll definitely revisit my notes on this.