August 15, 2019

Boundaries for algorithm analysis

Some boundaries you should know to approximate time and space complexity of your algorithm.

  • $2^{10} = 1,024 \approx 10^{3}, 2^{20} = 1,048,576 \approx 10^{6}$
  • 32-bit signed integers (int) and 64-bit signed integers (long long) have upper limits of $2^{31} − 1 \approx 2 \times 10^{9}$ (safe for up to $\approx 9$ decimal digits) and $2^{63} − 1 \approx 9 \times 10^{18}$ (safe for up to $\approx 18$ decimal digits) respectively.
  • Unsigned integers can be used if only non-negative numbers are required. 32-bit unsigned integers (unsigned int) and 64-bit unsigned integers (unsigned long long) have upper limits of $2^{32} − 1 \approx 4 \times 10^{9}$ and $2^{64} − 1 \approx 1.8 \times 10^{19}$ respectively.
  • There are $n!$ permutations and $2^{n}$ subsets (or combinations) of n elements.
  • The best time complexity of a comparison-based sorting algorithm is $Ω(n\log_{2}{n})$.

Notes:

  • The largest input size for typical programming contest problems must be < 1M. Beyond that, the time needed to read the input (the Input/Output routine) will be the bottleneck.
  • Usually, $O(n\log_{2}{n})$ algorithms are sufficient to solve most contest problems.
  • There are a number of studies to find smaller sorting algorithms, one of them could be found here.
  • If you need to store integers $\geq 2^{64}$, use the Big Integer technique.

to be continue…

© khanhtc 2019