0
$\begingroup$

what is the role of the constant of proportionality while comparing the the order of complexities of two competing algorithms.

Like in case ALGO A has complexity 3*O(n) while ALGO B has complexity 10*O(n),What will be the effect of constant of 3 and 10 here?

3 Answers 3

1

The constants have no effect at all -- "$3\cdot O(n)$ and "$10\cdot O(n)$" both describe the same class of functions.

0

The definition of f=O(g) is that there exists an n,m such that for every x>n, f(x) < M*g(x). that's why the constant doesn't matter. suppose ALGO A runs in 2*n binary operations, while ALGO B runs in n binary operations. then both run in O(n) time complexity.

  • 0
    so what is the difference between ALGO A and B ???2012-04-19
  • 1
    This is hard to tell, since $3 \cdot O(n) = 10 \cdot O(n)$. The only thing we can say is that the algorithms take roughly linear time in the size of the input.2012-04-19
  • 1
    @JohannesKloos: Strictly speaking, roughly linear time would be $\Theta(n)$, not $O(n)$.2012-04-19
  • 1
    @Aryabhata: True, but that was roughly what I meant by "roughly" :) I tend to assume that an algorithm will consume all its input, so it will have $\Omega(n)$ time-complexity.2012-04-19
  • 1
    @JohannesKloos: So, do you hate binary-search? :-) Just kidding...2012-04-19
  • 0
    @shariq There is no difference. we can even say that, for example, the algorithm for finding the minimum of an array of n numbers is O(n), and it's also 3*O(n), and 1.2345234234234*O(n). there is no difference. although n*O(n) is not the same as O(n), because n is not a constant.2012-04-20
0

you can judge the importance of constant of proportionality by comparing insertion sort (c1.n^2),and merge sort(c2.nlogn). insertion sort is better when n is small,because of only single reason ie c1