Ο  Υπολογισμός της Χρονικής Πολυπλοκότητας ενός αλγόριθμου εξαρτάτε από τον αριθμό επαναλήψεων του και από το μέγεθος εισόδου.
Η χρονική πολυπλοκότητα  αλγορίθμου T(n).
Με τον συμβολισμό T(n) ορίζουμε την συνάρτηση του χρόνου εκτέλεσης ενός αλγορίθμου ως προς το μέγεθος εισόδου n, δηλαδή τον αριθμό των βημάτων που εκτελούνται.
Μέγεθος Εισόδου ή στιγμιότυπου: αναφερόμαστε στο πλήθος δεδομένων που δέχεται ο αλγόριθμος στη είσοδό του. Τα δεδομένα θεωρούνται ότι βρίσκονται πάντα σε μια θέση μνήμης.
Χωρική πολυπλοκότητα: Μιλάμε για τον αριθμό θέσεων μνήμης που καταλαμβάνει και είναι απαραίτητες για τον αλγόριθμο για την εκτέλεσή του.

Για τον προσδιορισμό της χρονικής πολυπλοκότητας μας ενδιαφέρει η τάξη μεγέθους. Δοθείσης μιας συνάρτησης T(n) η τάξη μεγέθους της είναι ο μέγιστος βαθμός του n. Αν για παράδειγμα το n είναι υψωμένο σε δύναμη π.χ. n^2 και αποτελεί τον μεγαλύτερο βαθμό μέσα στην συνάρτηση τότε μιλάμε για βαθμό τάξης τετραγωνικό.

Ένα απλό παράδειγμα για κατανόηση του γιατί η χρονική πολυπλοκότητα είναι μια σημαντική διαδικασία που θα πρέπει να προσέξουμε είναι το παρακάτω.
έστω ένα πρόβλημα έχει δύο αλγορίθμους επίλυσης
Τον Α που είναι πολυωνυμικής τάξης μεγέθους n^3 και τον Β που είναι εκθετικής τάξης 2^n.
Αν με τη πρώτη ματιά ίσως να  μπορούμε να αποφασίσουμε ποιος είναι ο γρηγορότερος. Ας δούμε το γιατί. Για διαφορά μεγέθους εισόδου θα είναι

n Χρόνος-Βήματα Α Χρόνος-Βήματα Β
5 5^3 = 125 2^5=32
10 10^3 2^10=10^3
20 20^3= 10^4 2^10=10^6
100 100^3=10^6 2^100=10^30
1000 1000^3= 10^9 2^1000=10^300


Μέχρι για την τιμή εισόδου n=20 και οι δύο αλγόριθμοι δεν έχουν και μεγάλες διαφορές.
Ο χρόνος εκτέλεσης όμως αυξάνει δραματικά όταν αυξάνεται και το μέγεθος εισόδου. Μάλιστα στον εκθετικό αλγόριθμο για μόλις 100 βήματα εκτέλεσης ο αλγόριθμος θα επιλύσει το πρόβλημα σε χρόνο ίσο με την ηλικία του σύμπαντος! Φυσικά λοιπόν  ο αλγόριθμος Α είναι  και ο γρηγορότερος.

Πρακτικά θα ασχοληθούμε με την μελέτη του  αλγορίθμου Line Search.
ΑΛΓΟΡΙΘΜΟΣ  δεδομένα εισόδου [ A[ n ],  x ]
start
i=1
   while i<=n do 
            if A[ i ] =x then return i
            else  i:= i+1
   end while
return -1
end


Ο αλγόριθμος αναζητά σε ένα πίνακα Α το στοιχείο x. Στην καλύτερη περίπτωση που το x είναι στην πρώτη θέση του πίνακα τότε
Η while θα εκτελεσθεί μια φορά και ο χρόνος της θα είναι σταθερός Θ(n).
Στην χειρότερη περίπτωση η while θα εκτελεστεί n-1 φορές αφού το στοιχείο x είναι στην τελευταία θέση του πίνακα. Και πάλι ο χρόνος εκτέλεσης είναι γραμμικός δηλαδή Θ(n).
Η μέση περίπτωση είναι το στοιχείο x να είναι στην μέση του πίνακα. Τότε η while θα εκτελεστεί n/2 φορές δηλαδή n .1/2 =n δηλαδή ο χρόνος είναι ξανά γραμμικός.
Συνεπώς σε κάθε περίπτωση εκτέλεσης του αλγορίθμου έχουμε γραμμικό χρόνο εκτέλεσης Θ(n).

Ας δούμε ένα ακόμα παράδειγμα, του αλγορίθμου Sort (Ταξινόμηση Αύξουσα)
ΑΛΓΟΡΙΘΜΟΣ δεδομένα εισόδου [ Α[ n ], x ]
start
for i=1 to n-1
     for j=i+1 to n 
          if A[ i ] > A [ j ] then 
              swap ( A[ i ], A[ j ])
    end for
end for
end

Τα βήματα εκτέλεση του αλγορίθμου θα είναι

Τιμή iΤιμή j Αριθμός Βημάτων
i=1 j =2, 3,...nn-1
i=2 j =3, 4,...nn-2
i=3 j =4, 5,...nn-3
. . . . . . . . .
i=n-2 j=n-1, n 2
i=n-1 j=n 1
T(n)

Συνεπώς η σύνθεση του χρόνου του θα είναι





Θυμηθείτε στο σημείο αυτό ότι η μεγαλύτερη τάξη μεγέθους της συνάρτησης είναι η δύναμη του τετραγώνου.
Ένα χρήσιμο tip για τον υπολογισμό όταν υπάρχουν for  είναι ότι,  κάθε for  αυξάνει κατά ένα τον βαθμό του εκθέτη της συνάρτησης, δηλαδή στον παραπάνω κώδικα έχουμε 2 for οπότε θα είναι τουλάχιστον n^2
Καλή συνέχεια στην μελέτη  της  ΠΛΗ30.