divide and conquer

Για την επίλυση ενός υπολογιστικού προβλήματος Π έχουμε να επιλέξουμε μεταξύ τριών διαφορετικών αλγορίθμων «διαίρει και βασίλευε». Ο αλγόριθμος Α₁ διασπά το αρχικό πρόβλημα μεγέθους n σε 16 υποπροβλήματα μεγέθους n/4, τα επιλύει και στη συνέχεια συνθέτει τις λύσεις τους σε χρόνο n^3/2. Ο αλγόριθμος Α₂ διασπά το αρχικό πρόβλημα μεγέθους n σε 8 υποπροβλήματα μεγέθους n/8, τα επιλύει και στη συνέχεια συνθέτει τις λύσεις τους σε χρόνο 2n. Τέλος, ο αλγόριθμος Α₃διασπά το αρχικό πρόβλημα μεγέθους n σε 2 υποπροβλήματα μεγέθους n/7 και σε άλλα 2 υποπροβλήματα μεγέθους 2n/7, τα επιλύει και στη συνέχεια συνθέτει τις λύσεις τους σε χρόνο n.

A) Να γράψετε τις αναδρομικές εξισώσεις που δίνουν τον χρόνο εκτέλεσης των αλγορίθμων Α₁και A₂ και στη συνέχεια να τις επιλύσετε με χρήση του θεωρήματος της Κυριαρχίας.

B) Επαληθεύστε την απάντηση του υποερωτήματος (Α) για τον χρόνο εκτέλεσης T₂(n) του αλγορίθμου Α₂ με τη μέθοδο της αντικατάστασης, προσδιορίζοντας επακριβώς τη σταθερά n₀ και εκείνες (c₁, c₂) του ασυμπτωτικού συμβολισμού. Ως αρχική συνθήκη, ισχύει ότι 

Γ) Να γράψετε την αναδρομική εξίσωση που δίνει τον χρόνο εκτέλεσης του αλγορίθμου Α₃ και στη συνέχεια να την επιλύσετε με το δέντρο της αναδρομής.

Δ) Ποιος αλγόριθμος επιλύει χρονικά πιο αποδοτικά το υπολογιστικό πρόβλημα Π και γιατί;