0

A lot of people talks about them when Comparing algorithms. For example, when comparing quicksort and smoothsort, both have an average time complexity of O(nlogn), but they say that smoothsort is worst because "it has more hidden constants"

What does that mean?

Imnewhere
  • 13
  • 4
  • Related: http://stackoverflow.com/questions/22188851/why-is-constant-always-dropped-from-big-o-analysis – Caramiriel Apr 16 '16 at 17:26
  • Thanks, I quickly understood what that means. So basically, for big o notation O(n) and 0(2n) is the same, both are represented as O(n). But the second is slower because it has a hidden constant – Imnewhere Apr 16 '16 at 17:58

1 Answers1

0

Constant multipliers are dropped when analyzing the running time of an algorithm. For example 100*n is noted as O(n) and so it's 3*n. When someone talk about "hidden" constants, they are talking about these multipliers that were ignored.

It's worth noting that not only "hidden" constants but also the cost of the operations greatly influences the actual running time. For example, 10 divisions and assignments might take longer than 20 additions.

Daniel Rodriguez
  • 607
  • 6
  • 11