לדעתי,
הסיבוכיות של counting sort היא תטא של n+k כאשר n הוא מספר איברי המערך ו- 0..k-1 זה התחום שבו נמצאים כל האיברים. במקרה שלנו : k=n^2 ולכן הסיבוכיות תהיה תטא של n^2. לעומת זאת ב-radix sort הסיבוכיות היא תטא של d*(n+k (אם משתמשים ב-counting sort) כאשר n מוגדר כמו קודם. k- התחום שבו נמצאות הספרות (לפי בסיס n , התחום הוא 0 עד n-1 ולכן k=n) d- שווה ל-2 במקרה שלנו (מספר הספרות המקסימלי של איבר) ולכן הסיבוכיות היא תטא של n במקרה של radix sort. אני לא מומחה גדול בנושא של מבני נתונים - אבל נראה לי שאני צודק....
