سلام.
فکر میکنم خط چهارم راه حلتون درست نیست. به علاوه اینکه توجه کنید حتی اگر به همین جواب آخر هم می‌رسیدید، مرتبه‌ی جواب از n نمیشد و از مرتبه‌ی [tex]O(n^2)[/tex] میشد.

فکر میکنم راه حل سؤال به این شکل هست:

[tex]nT(n)=2\sum_{k=0}^{n-1}T(k) n[/tex]

[tex](n-1)T(n-1)=2\sum_{k=0}^{n-2}T(k) n-1[/tex]

[tex]nT(n)-(n-1)T(n-1)=2T(n-1) 1[/tex]

[tex]nT(n)=(n 1)T(n-1) 1[/tex]

[tex]T(n)=\frac{n 1}{n}T(n-1) \frac{1}{n}[/tex]

بعد از این برای پیدا کردن مرتبه، میشه از جایگذاری مکرر کمک گرفت:

[tex]T(n)=\frac{n 1}{n}(\frac{n}{n-1}(\frac{n-1}{n-2}...(\frac{n-n 2}{n-n 1})) \frac{1}{n})[/tex]

همانطور که می‌بینید، در این ضرب‌های مکرر، صورت و مخرج‌های پی‌درپی با هم ساده میشن، در نهایت فکر میکنم چیزی که می‌مونه اینطور میشه:
[tex]2(n 1)logn \in O(nlogn)[/tex]

چون [tex]\frac{1}{n}[/tex] در نهایت مرتبه‌ی logn داره و در جایگذاری مکرر هم دیدیم که یک مرتبه‌ی در logn ضرب خواهد شد.