If we have 2 algorthims. One of them is O() time-complexity and the other on is θ() time-complexity. Which one we prefer to solve our problem? and why?

CodePudding user response：

Making such comparisons between two different notations doesn't seem to be so meaningful to me, but here is the logic: θ indicates both an upper-bound and a lower-bound for the number-of-operations function of your algorithm. Whereas O indicates only an upper-bound. Therefore technically, a function with θ(1) time complexity is also O(nlogn). As to the question, I put my comment at the end of the explanation based on this logic.

θ(nlogn) time complexity means that number of operations your algorithm will perform is upper-bounded by nlogn and lower-bounded by nlogn, that is, number of operations will be constant multiple of nlogn.

O(nlogn) time complexity means that number of operations your algorithm will perform is upper-bounded by nlogn, that is, maximum number of operations will be constant multiple of nlogn.

Notice that, in second case we cannot make any comment on the minimum number of operations that can be performed. Any function can be said to be upper-bounded by nlogn as long as number of operations doesn't exceed a multiple of nlogn as input size goes to infinity. So your function can have constant time, or linear time, or logarithmic complexity. Since we have a possibility to have number of operations that is θ(n), θ(logn), θ(n1), etc. I would say that using the algorithm with O(nlogn) would be better.

CodePudding user response：

Let's try to compare the algorithms:

First algorithm has O(nlogn) time complexity which means that execution time t1 is

 t1 <= k1 * n * log(n)   o(n * log(n))

Second algorithm is θ(nlogn), that's why

 t2 = k2 * n * log(n)   o(n * log(n))

Assuming that n is large enough so we can neglect o(n * log(n)) term, we still have two possibilities here.

1. t1 < n * log(n)
2. t1 = k1 * n * log(n) (at least for some worst case)

In the first case we should prefer algorithm 2 for large n, since algorithm 1 has a shorter execution time when n is large enough.

In the second case we have to compare unknown k1 and k2, we have not enough information to choose from 1st and 2nd algorithms.