Question

Question about big-O notation:

If I know a given algorithm is O(N^2) and that it takes 10 seconds to process a given dataset, can I extrapolate the time another O(N^2) algorithm will take to process the same dataset? Would it be the same time? Or can I not assume that?

Answer 1

You cannot assume that. Big Oh notation is a measure of worst case. Furthermore, Big Oh is saying that the algorithm's computation is in the family of g(n) [where f(n) is Big Oh(g(n))]. This means that even if your data set is showing the worst case, your function may actually have complexity of n^2 + 5 n + c, where c is some constant, not simply n^2.

Answer 2

thanks that makes sense