2 ms·

This really only takes effect for very large values of n. The crossover is around 3x10^7 https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs+sqrt%28n%

• foota 5y ago
  In fairness, that's not _that_ huge of a graph.
  • zamadatix 5y ago
    General graph - no. Planar graph you're not sure would remain planar if you added another node - seems pretty large.
• dbaupp 5y ago
  It's somewhat meaningless to compute exact cross-overs for big-O complexities without the constant factors. That is, the actual times for the algorithms are C1 * sqrt(n) + ... and C2 * log(n)^3 + ..., where the ... are lower-order terms. The exact ratio of C1 and C2 (and even the lower-order terms) can have a large impact on the crossover: - C1 = C2 = 1 => cross-over is 2x10^7 - C1 = 1, C2 = 10 => cross-over is 2x10^10 - C1 = 10, C2 = 1 => cross-over is 1668.2!