CODEWITHSUNDEEP
algorithmtime-complexitybig-o
user17272418
user17272418

Reputation:

algorithm with O(logn) and θ(logn) time-complexity

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

Upvotes: 1

Views: 570

Answers (2)

kaya3
kaya3

Reputation: 51132

There is insufficient information given to decide which algorithm is preferable. It's possible that the first algorithm is preferable, it's possible that both are equally preferable, and it's even possible the second is preferable if they are asymptotically equal but the second has a lower constant factor.

  1. Consider the fact that binary search is O(n) because big-O only gives an upper bound, whereas linear search is Θ(n). Binary search is preferable, because it is asymptotically more efficient.
  2. Consider linear search, which is O(n), and... linear search, which is Θ(n). Both are equally preferable because they are literally the same.
  3. Consider bubble sort, which is O(n2), and insertion sort, which is Θ(n2). Insertion sort does on average ~ n2/4 comparisons, whereas bubble sort does on average ~ n2/2 comparisons, which is twice as many; so insertion sort is preferable.

So as you can see, it's not possible to say without more information.

Upvotes: 1

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186813

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.

Upvotes: 0

Related Questions