For a certain problem if I have a O(f1(m,n)) algorithm and a O(f2(m,n)) algorithm, can I have a O(min(f1(m,n),f2(m,n))) algorithm?

Actually, I have this question because of clrs 14.3.4 I know how to prove O(N)for traversal and O(klogN) for delete every time. so how to prove there exists O(min(N,klogN)) becomes a question. (I asked it in How to prove the time complexity of query in interval tree)

Assert this is correct, can any algorithms having a O(f1(m,n)) and a O(f2(m,n)) solution have a O(min(f1(m,n),f2(m,n))) solution(for m,n not known before execution).


  • Yes. If you have a O(f1(m,n)) and a O(f2(m,n)) solution, you could execute each of the solutions in pseudo-parallel (time-sliceing) and stop when one of them found the solution.

    This way you get an O(min(f1(m,n),f2(m,n))) algorithm.

    This is 2 times slower than performing the algorithm that found the solution first alone but that makes no difference according to the O-Notation (because 2 is only a constant factor).