Timeline for How to sort an array $A[1..i..n]$ where $A[i] \in \{1,2,..,n^5 \}$ in $\Theta (n)$ time?

11 events

when toggle format	what		by	license	comment
May 25, 2017 at 14:30	comment	added	rus9384		Why do you think that it's constant? If you'll take $n = 10^6$ you will receive a maximum number $n^5 = 10^{30}$ and it's length is 31 decimal digits (103 bits). If you'll convert that number into base $n$ it'll be represented as 5 24-bit strings.
May 25, 2017 at 14:04	comment	added	Yos		But there can be only 6 digits in a number at most, which is a constant.
May 25, 2017 at 14:02	comment	added	rus9384		That will divide number into 5 parts and what? Computer still works with them as with binary strings.
May 25, 2017 at 13:54	comment	added	Yos		But we converted all numbers into base $n$ so it's $\Theta(6n)$ time because there're only 6 unique digit lengths
May 25, 2017 at 13:33	comment	added	rus9384		Line 6, you call that function $n$ times and itself it takes $O(log(n))$ time.
May 25, 2017 at 13:24	comment	added	Yos		Which line are you referring to?
May 25, 2017 at 12:23	comment	added	rus9384		You have cycles where you show complexities O(n) and O(count digits) inside it. If you multiply them, it won't be linear.
May 25, 2017 at 7:34	comment	added	Yos		Actually I found a trick that we can convert the numbers to base $n$ which will allow us to achieve linear time complexity if my calculations are correct
May 24, 2017 at 20:00	history	edited	D.W.♦	CC BY-SA 3.0	added 9 characters in body
May 24, 2017 at 19:43	history	edited	rus9384	CC BY-SA 3.0	added 23 characters in body
May 24, 2017 at 19:17	history	answered	rus9384	CC BY-SA 3.0