עבור מספרים טבעיים \(a\) ו-\(b\) המיוצגים בבסיס עשרוני, נאמר ש-\(a\) חשוב יותר מ-\(b\) אם סכום הספרות של \(a\) גדול או שווה לסכום הספרות של \(b\). נתון מערך \(A\) בן \(n\) מספרים טבעיים, הציעו אלגוריתם המקבל כקלט את \(A\) ומספר טבעי \(k\) (בין \(1\) ל-\(n\)) ומדפיס את \(k\) האיברים החשובים ביותר ב-\(A\). יש לנתח את נכונותו וסיבוכיותו של האלגוריתם עבור שני המקרים הבאים:
א. לא נדרש שהאיברים יודפסו בסדר ממוין. במקרה זה על האלגוריתם לרוץ בזמן \(O(n)\) במקרה הגרוע.
ב. נדרש שהאיברים יודפסו בסדר ממוין וידוע ש-\(k = O(\sqrt{n})\).
הערה: ניתן להניח שחישוב סכום הספרות של מספר במערך מחושב ב-\(O(1)\). יש לתאר את האלגוריתם בקצרה באופן מילולי, אין לכתוב פסאודוקוד.