Οι Ασυμπτωτικοί Συμβολισμοί είναι ένα μαθηματικό εργαλείο σύγκρισης και εκτίμησης του χρόνου εκτέλεσης των αλγορίθμων.

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

Αυτό βέβαια εξαρτάτε από πολλούς παράγοντες ένας εκ των οποίων είναι και το μέγεθος των στιγμιοτύπων(περιπτώσεις εκτέλεσης) του. Αν ένα  στιγμιότυπο του αλγορίθμου πραγματοποιεί n βήματα εκτέλεσης τότε λέμε ότι έχει μέγεθος n, και απαιτεί ένα χρόνο τάξης T(n) για την υλοποίηση του, αν βέβαια  υπάρχει μια σταθερά c, και για κάποια υλοποίηση του αλγορίθμου , είναι ικανή να λύσει κάθε στιγμιότυπο του προβλήματος μεγέθους n σε χρόνο όχι περισσότερο από c.T(n) βήματα.

Έτσι λέμε ότι ένας αλγόριθμος είναι γραμμικός αν το T(n)  =n , ή πολυωνυμικός αν T(n)=n^2 ή n^3 κτλ. και εκθετικός αν ο T(n)= c^n δηλαδή 2^n ή 4^n κτλ.

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

Ο ασυμπτωτικός συμβολισμός αυτός χρησιμοποιείτε για να εκφράσει το σύνολο των συναρτήσεων g(n)  που έχουν την ίδια τάξη μεγέθους και για κάποια f(n) από αυτές ισχύει :

Θ(g(n))={f(n): υπάρχουν σταθερές τιμές c1,c2 και n0 | 0<=c1.g(n)<=f(n)<=c2.g(n) για κάθε n>n0}

Απλοποιώντας τον παραπάνω ορισμό θα πούμε ότι το lim f(n)/g(n) με n να τείνει στο άπειρο, θα πρέπει να είναι ίσο με c διαφορετικό  όμως του μηδενός. Τότε θα λέμε ότι η f(n) είναι Θ(g(n)).

Ο συμβολισμός αυτός μας βοηθά να εκφράσουμε ένα άνω φράγμα της τάξης μεγέθους της συνάρτησης. Δηλαδή  μια συνάρτηση g(n) ανήκει στο σύνολο ο(g(n)) και για κάποια f(n) από αυτές ισχύει : ο(g(n))={f(n): για κάθε σταθερές τιμές c υπάρχει n0 | 0<=f(n)<=c.g(n) για κάθε n=>n0.}

Εκφράζοντας τον ορισμό θα πούμε ότι lim f(n)/g(n) με n να τείνει στο άπειρο, θα πρέπει να είναι ίσο με 0.Τότε θα λέμε ότι η f(n) είναι ο(g(n)).

Ο συμβολισμός αυτός μας βοηθά να εκφράσουμε ένα κάτω φράγμα της τάξης μεγέθους της συνάρτησης. Δηλαδή  μια συνάρτηση g(n) ανήκει στο σύνολο ω(g(n)) και για κάποια f(n) από αυτές ισχύει : ω(g(n))= {f(n): για κάθε θετικές σταθερές τιμές c υπάρχει n0 | 0<=c.g(n)<= f(n) για κάθε n=>n0.}

Εκφράζοντας τον ορισμό θα πούμε ότι lim f(n)/g(n) με n να τείνει στο άπειρο, θα πρέπει να είναι ίσο με +οο. Τότε θα λέμε ότι η f(n) είναι ω(g(n)).

Μια συνάρτηση g(n) ανήκει στο σύνολο Ο(g(n)) όταν για μια f(n) ισχύει: 

 Ο(g(n))={f(n): υπάρχουν σταθερές τιμές c υπάρχει n0 | 0<=f(n)<=c.g(n) για κάθε n=>n0.}

Δηλαδή εδώ χρειαζόμαστε μόνο ένα ασυμπτωτικό άνω φράγμα.

Μια συνάρτηση g(n) ανήκει στο σύνολο Ω(g(n)) όταν για μια f(n) ισχύει: 

Ω(g(n))= {f(n): υπάρχουν θετικές σταθερές τιμές c υπάρχει n0 | 0<=c.g(n)<= f(n) για κάθε n=>n0.}

Δηλαδή εδώ χρειαζόμαστε μόνο ένα ασυμπτωτικό κάτω φράγμα.

Στο σημείο αυτό  θα πρέπει να τονίσουμε ότι για κάθε ζευγάρι συναρτήσεων f(n) και g(n) η f(n) =Θ(g(n)) αν και μόνο αν f(n)=Ο(g(n)) και f(n) =Ω(g(n)).

Δηλαδή το σύνολο Θ(g(n)) αποτελεί την τομή των συνόλων Ο(g(n)) που εκπροσωπεύει την χειρότερη περίπτωση για την πολυπλοκότητα του αλγορίθμου  και του συνόλου Ω(g(n)) που εκπροσωπεύει την καλύτερη περίπτωση για την πολυπλοκότητα του αλγορίθμου.

Ακόμα συμπεραίνουμε ότι το σύνολο ο(g(n)) εκπροσωπεύει όλες τις συναρτήσεις μικρότερης τάξης μεγέθους από την g(n)  ενώ το ω(g(n)) εκπροσωπεύει όλες τις συναρτήσεις μεγαλύτερης τάξης μεγέθους από την g(n).

Για τον υπολογισμό της εκτίμησης του φράγματος ή της τάξης μιας συνάρτησης, εφόσον δεν μας ενδιαφέρει ο ακριβείς υπολογισμός της, άλλωστε  εκφράζεται με ασυμπτωματικούς συμβολισμούς, μοντελοποιούμε την παράσταση της συνάρτησης με την βοήθεια λογαρίθμων. Την τακτική της μοντελοποίησης μιας συνάρτησης την γνωρίσατε  και από την ΠΛΗ20 με μια άλλη τακτική έμμεσου υπολογισμού, αυτή των γεννητριών συναρτήσεων.