3 added 9 characters in body edited May 24 '17 at 20:00 D.W.♦ 107k1414 gold badges143143 silver badges318318 bronze badges Radix sort for integers of arbitrary length has $$\mathcal{O}(mn)$$ time complexity, where m is the length of number. Count digits takes $$\mathcal{O}(log(n))$$$$\mathcal{O}(\log(n))$$ time, so, your cycle will take at least (in worst case though) $$\mathcal{O}(nlog(n))$$$$\mathcal{O}(n \log(n))$$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them. Of course, there exists an algorithm that can sort any array of numbers in $$\mathcal{O}(nlog(n)|log(n))$$ time|space$$\mathcal{O}(n \log(n))$$ time and $$O(\log(n))$$ space. Radix sort for integers of arbitrary length has $$\mathcal{O}(mn)$$ time complexity, where m is the length of number. Count digits takes $$\mathcal{O}(log(n))$$ time, so, your cycle will take at least (in worst case though) $$\mathcal{O}(nlog(n))$$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them. Of course, there exists an algorithm that can sort any array of numbers in $$\mathcal{O}(nlog(n)|log(n))$$ time|space. Radix sort for integers of arbitrary length has $$\mathcal{O}(mn)$$ time complexity, where m is the length of number. Count digits takes $$\mathcal{O}(\log(n))$$ time, so, your cycle will take at least (in worst case though) $$\mathcal{O}(n \log(n))$$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them. Of course, there exists an algorithm that can sort any array of numbers in $$\mathcal{O}(n \log(n))$$ time and $$O(\log(n))$$ space. 2 added 23 characters in body edited May 24 '17 at 19:43 rus9384 90144 silver badges1414 bronze badges Radix sort for integers of arbitrary length has $$\mathcal{O}(mn)$$ time complexity, where m is the length of number. Count digits takes $$\mathcal{O}(log(n))$$ time, so, your cycle will take at least (in worst case though) $$\mathcal{O}(nlog(n))$$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them. Of course, there exists an algorithm that can sort any array of numbers in $$\mathcal{O}(nlog(n)|log(n))$$ time|space. Radix sort for integers of arbitrary length has $$\mathcal{O}(mn)$$ time complexity, where m is the length of number. Count digits takes $$\mathcal{O}(log(n))$$ time, so, your cycle will take at least $$\mathcal{O}(nlog(n))$$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them. Of course, there exists an algorithm that can sort any array of numbers in $$\mathcal{O}(nlog(n)|log(n))$$ time|space. Radix sort for integers of arbitrary length has $$\mathcal{O}(mn)$$ time complexity, where m is the length of number. Count digits takes $$\mathcal{O}(log(n))$$ time, so, your cycle will take at least (in worst case though) $$\mathcal{O}(nlog(n))$$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them. Of course, there exists an algorithm that can sort any array of numbers in $$\mathcal{O}(nlog(n)|log(n))$$ time|space. 1 answered May 24 '17 at 19:17 rus9384 90144 silver badges1414 bronze badges Radix sort for integers of arbitrary length has $$\mathcal{O}(mn)$$ time complexity, where m is the length of number. Count digits takes $$\mathcal{O}(log(n))$$ time, so, your cycle will take at least $$\mathcal{O}(nlog(n))$$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them. Of course, there exists an algorithm that can sort any array of numbers in $$\mathcal{O}(nlog(n)|log(n))$$ time|space.