Θέμα: Υπολογισμός χρόνου εκτέλεσης (υπολογισμός αριθμού πράξεων των εντολών)

[Diotima]

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

[theoni]

Καλησπέρα η ερώτηση έχει ξαναγίνει αλλά  δεν μπόρω να βρω την απάντηση!το ι<--ι+1 μετράει για μια πράξη σε οποιαδήποτε δομή επανάληψης το ι<--ι+α μετράει για 2 πράξεις όπως και το ι<--γ+δ σωστά?

[alkisg]

Χμμ νομίζω ότι θα εξηγήσω καλύτερα τι πιστεύω για το uniform cost model χρησιμοποιώντας το για να (ξανα)απαντήσω σε αυτό το μήνυμα του Γιώργου:

Πχ ο αλγόριθμος
Διάβασε ν
Για ι από 1 μέχρι ν
   Γράψε ι
Τέλος_επανάληψης
Έχει εκθετική πολυπλοκότητα. Το μέγεθος εισόδου είναι το πλήθος των ψηφίων δηλαδή log(ν). Έτσι έχω f(log(ν))=ν που είναι εκθετική (αν θέλεις όπου log(ν) το x θα βγει το εκθετικό).

Ισχυρίζεσαι ότι το γράψιμο ν στοιχείων έχει εκθετική πολυπλοκότητα.
Εγώ ισχυρίζομαι ότι έχει γραμμική (στο uniform cost model που θεωρώ ότι είναι και αυτό που χρησιμοποιούμε στην ΑΕΠΠ).

Στο uniform cost model, το πόσα bit είναι το "ν" δεν μας ενδιαφέρει καθόλου. Θεωρούμε ότι οι αριθμοί μας εκφράζονται από έναν σταθερό πλήθος ψηφίων "c", π.χ. c=32 στους 32-bit επεξεργαστές.
Το σημείο κλειδί είναι ότι το c δεν είναι ίσο με log(ν) όπως αναφέρεις, είναι ανεξάρτητη σταθερά από το ν.
Τους αριθμούς μας θα τους χρειαστούμε για να βάλουμε κι άλλα πράγματα μέσα (π.χ. ένα sum <- sum+i), δεν θα βάλουμε μόνο το ν σε αυτούς.
Στην Διάβασε ν, σε κάθε περίπτωση θα διαβάσουμε c bits, όχι log(ν) bits.
Έτσι για π.χ. c=32 και ν=10, τα δυαδικά ψηφία της εισόδου μας δεν θα είναι "1010", αλλά "00000000 00000000 00000000 00001010", ένας ολόκληρος 32bit αριθμός.

Οπότε τελικά το μέγεθος της εισόδου σε bit είναι "c", σε ακεραίους είναι "ένας", και η πολυπλοκότητα του παραπάνω αλγορίθμου δεν μπορεί να μετρηθεί με βάση το μέγεθος της εισόδου παρά μόνο με βάση την τιμή "ν" της εισόδου όπου και είναι γραμμική.

Παρεμπιπτόντως Γιώργο, αν ήθελες να υλοποιήσεις την εντολή "Διάβασε" με "ν" bits και όχι "c" bits εισόδου, θα χρειαζόσουν επανάληψη και κόστος Ο(log(ν)), δεν θα μπορούσε να υλοποιηθεί σε Ο(1). Προφανώς λοιπόν χωρίς Ο(1) δεν θα χρησιμοποιούσες uniform cost model.

[gpapargi]

Διαφωνούμε στον τρόπο που ερμηνεύουμε τα uniform και logarithmic cost model Άλκη. Εσύ ερμηνεύεις το logarithmic cost model ως «τα πάντα μετρώνται με βάση το πλήθος των bits και η είσοδος και οι πράξεις». Εγώ το ερμηνεύω μόνο σαν ένα μοντέλο που μου λέει πόσα βήματα μετράω σε κάθε πράξη μου (πχ πρόσθεση, διαίρεση ανάθεση τιμής κλπ). Σε καμία περίπτωση δεν βάζω το uniform στο μέγεθος εισόδου. Αυτή είναι η βασική διαφωνία μας. Ο λόγος που κατά τη γνώμη μου δεν επιτρέπεται είναι ότι με αυτό τον τρόπο δεν μπορείς να φανταστείς το μέγεθος εισόδου να απειρίζεται. Δεν μπορείς δηλαδή ταυτόχρονα να λες ότι απειρίζεται το μέγεθος εισόδου και να έχεις και φραγμένο πλήθος bits στην είσοδο όσο μεγάλο και να είναι αυτό. Και αν δεν επιτρέπεις στην είσοδο να απειρίζεται δεν μπορείς να μιλάς για ασυμπτωτικές συμπεριφορές και συμβολισμούς Ο για τους λόγους που εξήγησα σε προηγούμενο μήνυμα.

Θα δώσω και ένα τελείως χειροπιαστό παράδειγμα χωρίς καμία αυστηρότητα για να γίνει κατανοητό αυτό που λέω για την εκθετική πολυπλοκότητα.
Έστω ότι διαβάζω 5 αριθμούς, τους 1,2,3,4,5 και τους βάζω σε ένα μονοδιάστατο πίνακα, τον κάθε αριθμό σε ένα κελί. Κάνω σειριακή. Προφανώς έχω 5 βήματα και Ο(ν).
Έστω τώρα ότι με τους 5 αυτούς αριθμούς κάνω κάτι άλλο: φτιάχνω τον ακέραιο αριθμό 12345. Και εκτυπώνω με μια Για τους αριθμούς από το 1 μέχρι τον 12345. Κάνω 12345 βήματα. Αυτό θα πει εκθετική πολυπλοκότητα. Και στους 2 αλγορίθμους έχω ίδια είσοδο, τα 5 ψηφία. Στον ένα κάνω 5 βήματα και στον άλλο 12345. Η μια είναι γραμμική και η άλλη είναι εκθετική πολυπλοκότητα.

[alkisg]

Δεν θέλουμε να μεγαλώσουμε/απειρίσουμε την είσοδο. Θέλουμε να μεγαλώσουμε το μέγεθος του προβλήματος, που άλλοτε συμπίπτει και με το μέγεθος της εισόδου, άλλοτε με την τιμή της, όπως γράφει και η wikipedia.
Στο συγκεκριμένο παράδειγμα αυτό γίνεται μεγαλώνοντας την τιμή του ν όσο θέλουμε.
Και εννοείται ότι το σχετικό σταθερό c που θα χρειαστούμε θα είναι αρκετά μεγάλο ώστε να χωρέσει το ν που θα διαβάσουμε.
Δεν υπάρχει κανένα φράγμα.

Επίσης δεν απάντησες στο "αφού υλοποιείς την "Διάβασε ν" με ν bits, δεν έχεις πια Ο(1) αλλά O(log(ν)) για την εντολή Διάβασε, άρα δεν χρησιμοποιείς uniform model όπως λες".

Συνάδελφοι, υπάρχει κάποιος άλλος εκτός από τον Γιώργο που να θεωρεί ότι το παρακάτω παράδειγμα στα πλαίσια της ΑΕΠΠ έχει εκθετική πολυπλοκότητα;

Πχ ο αλγόριθμος
Διάβασε ν
Για ι από 1 μέχρι ν
   Γράψε ι
Τέλος_επανάληψης
Έχει εκθετική πολυπλοκότητα. Το μέγεθος εισόδου είναι το πλήθος των ψηφίων δηλαδή log(ν). Έτσι έχω f(log(ν))=ν που είναι εκθετική (αν θέλεις όπου log(ν) το x θα βγει το εκθετικό).

Αν ναι, αξίζει να το παλέψουμε περισσότερο, αλλιώς αφού εντοπίσαμε τη διαφωνία, δεν υπάρχει πρόβλημα να μείνουμε εκεί...

[itt]

Εγώ δεν αναλύω την πολυπλοκότητα, ίσα ίσα λέω ότι δεν ορίζεται η πολυπλοκότητα ως προς τα bits της εισόδου. Πώς να δώσω μέση τιμή από κάτι που δεν ορίζεται;

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

Συνάδελφοι, υπάρχει κάποιος άλλος εκτός από τον Γιώργο που να θεωρεί ότι το παρακάτω παράδειγμα στα πλαίσια της ΑΕΠΠ έχει εκθετική πολυπλοκότητα;
Αν ναι, αξίζει να το παλέψουμε περισσότερο, αλλιώς αφού εντοπίσαμε τη διαφωνία, δεν υπάρχει πρόβλημα να μείνουμε εκεί...

Μπορείς να πεις ότι έχει πολυωνυμική πολυπλοκότητα, αφού όντως έχει ψευδοπολυωνυμική πολυπλοκότητα και δεν νομίζω ότι υπάρχει κάποιο νόημα να
διδαχθεί η διαφορά τους.

[ether]

Συνάδελφοι, υπάρχει κάποιος άλλος εκτός από τον Γιώργο που να θεωρεί ότι το παρακάτω παράδειγμα στα πλαίσια της ΑΕΠΠ έχει εκθετική πολυπλοκότητα;
Αν ναι, αξίζει να το παλέψουμε περισσότερο, αλλιώς αφού εντοπίσαμε τη διαφωνία, δεν υπάρχει πρόβλημα να μείνουμε εκεί...

Πχ ο αλγόριθμος
Διάβασε ν
Για ι από 1 μέχρι ν
   Γράψε ι
Τέλος_επανάληψης
Έχει εκθετική πολυπλοκότητα. Το μέγεθος εισόδου είναι το πλήθος των ψηφίων δηλαδή log(ν). Έτσι έχω f(log(ν))=ν που είναι εκθετική (αν θέλεις όπου log(ν) το x θα βγει το εκθετικό).

Κάτι τέτοιο θα σήμαινε ότι και ο κλασικός αλγόριθμος δυναμικού προγραμματισμού για το knapsack με πολυπλοκότητα O(nW) στα πλαίσια της ΑΕΠΠ είναι πολυωνυμικός, άρα στα πλαίσια της ΑΕΠΠ P=NP.
Θεωρώ προτιμότερο να πω σε έναν μαθητή "Είναι εκτός ύλης ΑΕΠΠ ο υπολογισμός της πολυπλοκότητας του παραπάνω αλγορίθμου".

[alkisg]

Βρήκα αντίστοιχο παράδειγμα στη βιβλιογραφία (υπολογισμό του r = x^y με επαναληπτικούς πολλαπλασιασμούς):
https://books.google.gr/books?id=Yxxw90d9AuMC&pg=PA3&redir_esc=y#v=onepage&q&f=false - τέλος σελίδας 3.

Στο uniform model αναφέρει ότι η πολυπλοκότητά του είναι πολυωνυμική και ίση με 2+3*y. Την μετράει ως προς την τιμή του y. Δεν την μετράει ως προς το πλήθος των bits και δεν την λέει εκθετική - αν και ακριβώς παρακάτω αναφέρει ότι τυπικά μετράμε το input size σε bits. Ακόμα και μετά τον ορισμό του input size, στη σελίδα 6, συνεχίζει να αναφέρει το πρόβλημα ως Ο(y) στο uniform model.

Εξηγεί και το πρόβλημα των μεγεθών στο uniform καθώς και το πρόβλημα του ότι στο λογαριθμικό μοντέλο, μια εντολή a := b + 5 κοστίζει log|b| + log5, οπότε καταλαβαίνουμε ότι σίγουρα δεν θέλουμε το λογαριθμικό μοντέλο στην ΑΕΠΠ.

[gpapargi]

Επίσης δεν απάντησες στο "αφού υλοποιείς την "Διάβασε ν" με ν bits, δεν έχεις πια Ο(1) αλλά O(log(ν)) για την εντολή Διάβασε, άρα δεν χρησιμοποιείς uniform model όπως λες".

Δεν απάντησα γιατί φοβήθηκα ότι θα μπλέξουμε κι άλλο. Απαντάω. Καταρχήν ναι αν πρέπει να βάλω βάρος στην είσοδο που τείνει να απειρίζεται δεν μπορώ να δώσω σταθερά. Θέλω κόστος για κάθε bit, άρα πάω με λογαριθμικό ως προς τον αριθμό εισόδου υποχρεωτικά αλλιώς έχω ασυνέπεια στη σκέψη μου. Όμως υπάρχουν 2 ζητήματα.
Το πρώτο είναι ότι δεν μετράω στην πολυπλοκότητα και το Διάβασε γιατί θα την αλλοίωνα. Για παράδειγμα δεν τη δυαδική αναζήτηση. Διαβάζω ν αριθμούς και τους βάζω σε πίνακα (ν βήματα). Και μετά κάνω δυαδική (logn βήματα). Η ίδια η διάβασε είναι πιο επιβαρυντική από την βασική επεξεργασία μου. Δηλαδή μετράω το επεξεργαστικό μέρος αλλιώς αν βάλω και την ίδια την πράξη της εισόδου θα βγάλω γραμμική τη δυαδική αναζήτηση λόγω εισόδου.
Το δεύτερο είναι ότι δεν ευθύνεται η το logarithmic cost model για την εκθετικότητα του αλγορίθμου μου. Ευθύνονται οι εκθετικά πολλές διαιρέσεις. Αυτό ουσιαστικά λέω. Ότι και μια πράξη να μετρήσεις για την κάθε διαίρεση πάλι εκθετικά βγαίνουν τα βήματα. Όχι λόγω cost model άλλα λόγω εκθετικού πλήθους διαιρέσεων.

[gpapargi]

Να θέσω κι εγώ ένα ερώτημα που πηγάζει από το σχόλιο του Ether.
Ο κλασσικός αλγόριθμος ελέγχου πρώτου κάνοντας όλες τις διαιρέσεις είναι:

Διάβασε ν
πλήθος_διαιρετών <--0
Για ι από 1 μέχρι ν
  Αν ν mod ι =0 τότε
    πλήθος_διαιρετών<--πλήθος_διαιρετών +1
  Τέλος_αν
Τέλος_επανάληψης

Αν πλήθος_διαιρετών=2 τότε
   Γράψε 'πρώτος'
αλλιώς
  Γράψε 'σύνθετος'
Τέλος_αν

Στη βιβλιογραφία θεωρείται εκθετική πολυπλοκότητας. Ελπίζω μέχρι εδώ να συμφωνούμε.

Το ερώτημα είναι: στο πλαίσιο του μαθήματος είναι γραμμικός;
Αν κάποιος πιστεύει ότι είναι γραμμικός, η ένστασή μου είναι προφανής: Αλλοιώνουμε τα πράγματα και δεν μπορούμε να το κάνουμε.

[gpapargi]

Βρήκα αντίστοιχο παράδειγμα στη βιβλιογραφία (υπολογισμό του r = x^y με επαναληπτικούς πολλαπλασιασμούς):
https://books.google.gr/books?id=Yxxw90d9AuMC&pg=PA3&redir_esc=y#v=onepage&q&f=false - τέλος σελίδας 3.

Στο uniform model αναφέρει ότι η πολυπλοκότητά του είναι πολυωνυμική και ίση με 2+3*y. Την μετράει ως προς την τιμή του y. Δεν την μετράει ως προς το πλήθος των bits και δεν την λέει εκθετική - αν και ακριβώς παρακάτω αναφέρει ότι τυπικά μετράμε το input size σε bits. Ακόμα και μετά τον ορισμό του input size, στη σελίδα 6, συνεχίζει να αναφέρει το πρόβλημα ως Ο(y) στο uniform model.

Εξηγεί και το πρόβλημα των μεγεθών στο uniform καθώς και το πρόβλημα του ότι στο λογαριθμικό μοντέλο, μια εντολή a := b + 5 κοστίζει log|b| + log5, οπότε καταλαβαίνουμε ότι σίγουρα δεν θέλουμε το λογαριθμικό μοντέλο στην ΑΕΠΠ.

Θα το διαβάσω και αναλυτικά Άλκη το κομμάτι που δίνεις, αλλά πρόσεξε κάτι: Γράφει και την πολυπλοκότητα που προκύπτει από το λογαριθμικό μοντέλο και δεν είναι εκθετική. Είναι κάτι σαν πολυονυμική επί λογάριθμο. Είναι αυτό που σου λέω... δεν ευθύνεται το λογαριθμικό μοντέλο για την εκθετικότητα του αλγορίθμου που δίνω αλλά το εκθετικά μεγάλο πλήθος διαιρέσεων.

[alkisg]

Στη βιβλιογραφία το trivial primality test αναφέρεται ως γραμμικό ως προς την τιμή (=ουσιαστικά uniform model) και εκθετικό ως προς τα bits της εισόδου (=ουσιαστικά logarithmic model).
Προφανώς και στο συγκεκριμένο πρόβλημα οι παραδοχές του uniform είναι παρατραβηγμένες (το log(ν) γίνεται πολύ μεγαλύτερο από τα τυπικά c) οπότε συνήθως για σωστότερα αποτελέσματα μελετάται με το λογαριθμικό μοντέλο.

Η παλιά βιβλιογραφία συνήθως (αλλά όχι αποκλειστικά) δουλεύει με uniform στους απλούς αλγορίθμους όπου ο απειρισμός του προβλήματος συνδέεται με την αύξηση του πλήθος των units (π.χ. πίνακας με Ν στοιχεία) και με logarithmic σε αυτούς που απειρίζονται τα bits του τύπου δεδομένων ή έχουμε bit stream (π.χ. πρώτοι, κρυπτογράφηση, συμπίεση κλπ). Η καινούργια βιβλιογραφία συνήθως δουλεύει με integer RAM model, αλλά ας μην μπλέξουμε και με άλλα.

Εγώ θεωρώ ότι η ΑΕΠΠ χρησιμοποιεί το uniform, οπότε σαν απάντηση στον ether, όσα περιγράφονται σωστότερα με το logarithmic, αυτά είναι που θα χαρακτήριζα εκτός ύλης. Άρα το primality test ως προς την τιμή θα το θεωρούσα εντός ύλης, ενώ ως προς τα bits εισόδου εκτός ύλης.

Εσένα Γιώργο αν κατάλαβα καλά η βασική σου ένσταση είναι ότι ποτέ δεν δέχεσαι κάτι άλλο από τα bits της εισόδου για την μέτρηση της πολυπλοκότητας ενός προβλήματος. Οι υπόλοιπες διαφωνίες μας μάλλον είναι αποτέλεσμα αυτής. Σωστά;

Ενώ εγώ κάτω από τις κατάλληλες προϋποθέσεις και ανεξαρτήτως μοντέλου δέχομαι και την τιμή (που χρησιμοποιεί και το βιβλίο που παρέπεμψα), και την διαφορά της τιμής α-β, και τις διαστάσεις των πινάκων n,m (που χρησιμοποιεί και το βιβλίο της ΑΕΠΠ) κλπ ως μεταβλητές υπολογισμού της πολυπλοκότητας.

Μήπως αυτό βοηθήσει να ξεκολλήσουμε από τα bits της εισόδου; Σε αυτούς τους αλγόριθμους η πολυπλοκότητα για να εκφραστεί σωστά χρειάζεται και τα bits της εξόδου:
https://en.wikipedia.org/wiki/Output-sensitive_algorithm

Γενική συζήτηση για τις παραδοχές που κάνουμε, όπου αναφέρει ότι και ο υπολογισμός με βάση την τιμή είναι αποδεκτός τρόπος:
https://en.wikipedia.org/wiki/Context_of_computational_complexity

[ether]

Βρήκα αντίστοιχο παράδειγμα στη βιβλιογραφία (υπολογισμό του r = x^y με επαναληπτικούς πολλαπλασιασμούς):
https://books.google.gr/books?id=Yxxw90d9AuMC&pg=PA3&redir_esc=y#v=onepage&q&f=false - τέλος σελίδας 3.

Στο uniform model αναφέρει ότι η πολυπλοκότητά του είναι πολυωνυμική και ίση με 2+3*y. Την μετράει ως προς την τιμή του y. Δεν την μετράει ως προς το πλήθος των bits και δεν την λέει εκθετική - αν και ακριβώς παρακάτω αναφέρει ότι τυπικά μετράμε το input size σε bits. Ακόμα και μετά τον ορισμό του input size, στη σελίδα 6, συνεχίζει να αναφέρει το πρόβλημα ως Ο(y) στο uniform model.

Λέει ότι είναι 2+3*y. Τη χαρακτηρίζει όμως κάπου ως πολυωνυμική; Στις σελίδες 3 και 4 που διάβασα (λίγο βιαστικά είναι η αλήθεια) δεν είδα να χαρακτηρίζει το 2+3*y ως πολυωνυμικό.

[gpapargi]

Απαντάω ξεχωριστά σε αυτό γιατί μάλλον είναι το πιο σημαντικό από όλα.

Εσένα Γιώργο αν κατάλαβα καλά η βασική σου ένσταση είναι ότι ποτέ δεν δέχεσαι κάτι άλλο από τα bits της εισόδου για την μέτρηση της πολυπλοκότητας ενός προβλήματος. Οι υπόλοιπες διαφωνίες μας μάλλον είναι αποτέλεσμα αυτής. Σωστά;

Περίπου αλλά όχι ακριβώς. Δέχομαι και τα αριθμητικά πολλαπλάσια των bits εισόδου, όπως πχ τα ψηφία, τις λέξεις, τα bytes και κάθε πολλαπλάσιο γιατί δεν μου αλλάζουν την τάξη και καταλήγουν και σε πιο βολικές μεταβλητές. Το κρίσιμο σημείο είναι το εξής: Σε ένα πίνακα με ν στοιχεία τα οποία έχουν άνω φραγμένο μέγεθος για τη μεταβλητή που μπαίνει σε κάθε κελί,  το πλήθος των στοιχείων του πίνακα είναι τελικά πολλαπλάσιο των bits. Άρα δεν έχω πρόβλημα σε οποιοδήποτε πίνακα με μέγιστο μήκος σε κάθε μεμονωμένο κελί, να βρίσκω την πολυπλοκότητα με βάση των πλήθος των κελιών. Έτσι καταλήγω σε γραμμική πολυπλοκότητα στη σειριακή. Δεν μπορώ όμως να το κάνω αυτό στον έλεγχο πρώτου ή στον πίνακα που ο αριθμός σε κάθε κελί μπορεί να αυξάνει απεριόριστα.

[ether]

Βρήκα αντίστοιχο παράδειγμα στη βιβλιογραφία (υπολογισμό του r = x^y με επαναληπτικούς πολλαπλασιασμούς):
https://books.google.gr/books?id=Yxxw90d9AuMC&pg=PA3&redir_esc=y#v=onepage&q&f=false - τέλος σελίδας 3.

Στο uniform model αναφέρει ότι η πολυπλοκότητά του είναι πολυωνυμική και ίση με 2+3*y. Την μετράει ως προς την τιμή του y. Δεν την μετράει ως προς το πλήθος των bits και δεν την λέει εκθετική - αν και ακριβώς παρακάτω αναφέρει ότι τυπικά μετράμε το input size σε bits. Ακόμα και μετά τον ορισμό του input size, στη σελίδα 6, συνεχίζει να αναφέρει το πρόβλημα ως Ο(y) στο uniform model.

Εξηγεί και το πρόβλημα των μεγεθών στο uniform καθώς και το πρόβλημα του ότι στο λογαριθμικό μοντέλο, μια εντολή a := b + 5 κοστίζει log|b| + log5, οπότε καταλαβαίνουμε ότι σίγουρα δεν θέλουμε το λογαριθμικό μοντέλο στην ΑΕΠΠ.

Το βιβλίο που αναφέρεις, στη σελίδα 4 λέει:
"...
In the following, we will refer to the uniform cost model in all (time and space) complexity evaluations performed.
..."

Στο τέλος της σελίδας 5, ξεκινάει να αναλύει την πολυπλοκότητα του τετριμμένου αλγορίθμου (που ελέγχει όλους τους δυνατούς διαιρέτες μέχρι την τετραγωνική ρίζα του αριθμού) για έλεγχο πρώτου (ουσιαστικά του αλγορίθμου που ανέφερε πιο πάνω ο gpapargi, αν αλλάξει η τιμή μέχρι στη ΓΙΑ). Λέει ότι αν ο αριθμός x είναι πρώτος, ο αλγόριθμος εκτελεί πλήθος βημάτων ανάλογο του ρίζα(x).
Η σελίδα 6 δεν είναι διαθέσιμη στην προεπισκόπηση, στην αρχή της σελίδας 7 όμως αναφέρει ότι το κόστος εκτέλεσης είναι ανάλογο του 2^(n/2), (σελ 5)"...if we use the natural encoding scheme which represents integer x as a binary string of length n = logx".

Και αναφέρει:
¨...
Even if the two values are equal, the second one gives greater evidence of the complexity of the algorithm, which grows exponentially with the size of the input.
..."

Κι αυτός λοιπόν, που έχει δηλώσει ότι θα χρησιμοποιεί το uniform cost model, εκθετικό θεωρεί τον τετριμμένο αλγόριθμο για τον έλεγχο πρώτου αριθμού.

Και παρακάτω λέει ότι δεν είναι γνωστό μέχρι τώρα (δηλαδή τότε που έγραφε το βιβλίο) αν υπάρχει αλγόριθμος πολυωνυμικού χρόνου για το συγκεκριμένο πρόβλημα. Προφανώς εννοεί ντετερμινιστικός, γιατί πιθανοτικοί υπήρχαν και τότε. Τώρα βέβαια ξέρουμε ότι υπάρχει πολυωνυμικός ντετερμινιστικός (AKS), αν και στην πράξη χρησιμοποιούνται πιθανοτικοί.

Και καταλήγει λέγοντας:
"...
Notice that using a unary base encoding (an unnatural scheme) would result in an evaluation of the execution cost as the square root of the instance size.
..."