Αλγόριθμοι: Διαφορά μεταξύ των αναθεωρήσεων

Αν οι συναρτήσεις F και W είναι ίσες, τότε ο αλγόριθμος Α είναι βέλτιστος. Αν
όχι, σημαίνει ότι υπάρχει καλύτερος αλγόριθμος ή καλύτερο κάτω όριο. Παρατηρείστε ότι η

ότι η ανάλυση ενός αλγορίθμου δίνει ένα άνω όριο των βασικών πράξεων και ένα θεώρημα για την

για την F δίνει ένα κάτω όριο στις βασικές πράξεις για κάθε αλγόριθμο στην κλάση, στη χειρότερη περίπτωση.

Η έννοια του κάτω ορίου για τη συμπεριφορά της χειρότερης περίπτωσης των αλγορίθμωναλγο

ρίθμων στη συγκεκριμένη κλάση, είναι πολύ σημαντική στην υπολογιστική πολυπλοκότητα.
Πρέπει να κρατήσουμε καλά στο μυαλό μας ότι: " η F είναι ένα κάτω όριο για μια κλάση αλγορίθμων", σημαίνει ότι για κάθε αλγόριθμο στην κλάση και για κάθε είσοδο τάξης n, υπάρχει κάποια

υπάρχει κάποια είσοδος τάξης n, για την οποία ο αλγόριθμος πρέπει να εκτελέσει τουλάχιστοντουλάχι
στον F(n) βασικές πράξεις.