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
    @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