حل تشریحی سوال شماره 14 ساختمان داده ها و طراحی الگوریتم ها

فرض کنید p(x) و q(x) دو چند جمله ای درجه n-1 باشند و بخواهیم حاصل ضرب این دو چند جمله ای را با توجه به اینکه p و q را می توان به صورت زیر نوشت، به کمک یک الگوریتم تقسیم و حل به دست آورد.

$p\left(x\right)=P_L\left(x\right)+x_{}^{\frac{n}{2}}{P}_R\left(x\right),q\left(x\right)=q_L\left(x\right)+x_{}^{\frac{n}{2}}{q}_R\left(x\right)$

که در آن، $P_L$، $P_R$، $q_L$ و $q_R$ چند جمله ای هایی از درجه حداکثر $\frac{n}{2}-1$ هستند. پیچیدگی زمانی بهترین الگوریتم تقسیم و حل برای حل این مسئله کدام است؟