Γιώργο δεν νομίζω ότι θα βρεις κάπου στη βιβλιογραφία να αναφέρουν ότι η σειριακή αναζήτηση έχει εκθετική πολυπλοκότητα... κι αυτό επειδή ως βασική μονάδα εισόδου αριθμητικών δεδομένων θεωρούμε τη λέξη (word) του επεξεργαστή, όχι το bit.
Κι αυτό με τη σειρά του γίνεται επειδή τα bit κάθε λέξης επεξεργάζονται παράλληλα από την CPU σε Ο(1) με τις αντίστοιχες εντολές assembly, είτε αυτός είναι ακέραιος είτε πραγματικός.
Βέβαια για να γίνουν οι παραπάνω πολύ λογικές παραδοχές, κατά την μελέτη της πολυπλοκότητας θεωρούμε ότι τα δεδομένα μας δεν υπερβαίνουν το μέγεθος της λέξης του επεξεργαστή, και επίσης ότι δεν χρειάζεται βιβλιοθήκη αριθμών άπειρης ακρίβειας.
Επιτρέπεται όμως ο compiler να κάνει emulation λέξης μεγέθους π.χ. 64 bit σε επεξεργαστή 32 bit, δηλαδή τεχνητή αύξηση του μεγέθους λέξης, χωρίς να μας επηρεάζει στη μελέτη της πολυπλοκότητας, αφού το emulation γίνεται σε σταθερό χρόνο, άρα πάλι Ο(1).
Στη συνέχεια θέτεις ένα παραπλήσιο, αλλά διακριτό θέμα, την μελέτη των αλγορίθμων όταν η είσοδος τείνει στο άπειρο. Αυτό συνήθως δεν αναφέρεται στο μέγεθος των αριθμών της εισόδου (που θα αφορούσε μέγεθος λέξης ή βιβλιοθήκη αριθμών άπειρης ακρίβειας), αλλά στο πλήθος των αριθμών της εισόδου (που αφορά το μέγεθος της RAM). Δηλαδή θεωρούμε ότι αυξάνουμε το μέγεθος του προβλήματος δίνοντας περισσότερους αριθμούς, όχι μεγαλύτερους (που να μην χωράνε σε μια λέξη).
Θεωρώ ότι κατά τη μελέτη πολυπλοκότητας αλγορίθμων, και το μέγεθος της λέξης και το μέγεθος της RAM τα θεωρούμε "επαρκή" για το πρόβλημα που έχουμε να λύσουμε, σταθερά και όσο μεγάλα χρειαζόμαστε αλλά όχι άπειρα, με κόστος χρήσης τους Ο(1).
Επίσης μια τελευταία παρατήρηση είναι ότι αν για κάποιο τραβηγμένο λόγο επιμέναμε ότι θέλουμε να αγνοήσουμε την αρχιτεκτονική των επεξεργαστών που είναι οργανωμένη σε λέξεις, και να αρχίσουμε να τα μετράμε όλα σε bit, τότε αυτό θα ήταν παραπλήσιο με τη χρήση βιβλιοθήκης αριθμών άπειρης ακρίβειας, και θα είχε σαν αποτέλεσμα ούτε οι βασικές πράξεις ούτε η προσπέλαση πινάκων να γίνεται πια σε Ο(1). Ούτε καν η προσπέλαση της RAM δεν θα γινόταν σε Ο(1), αφού δεν θα ήταν πια οργανωμένη σε λέξεις περιορισμένων bits. Ο απόλυτος χαμός. Θα χρειαζόμασταν διδακτορικό μόνο και μόνο για να μελετήσουμε την πολυπλοκότητα της σειριακής αναζήτησης... α πα πα!

Αν αντίθετα δεχτούμε όλα τα παραπάνω περί λέξεων κλπ, η σειριακή αναζήτηση γίνεται σε Ο(Ν) και γενικά όλα επιστρέφουν στο κανονικό.
Υ.Γ. ήθελα να αναφέρω ότι αντίστοιχες παραδοχές ισχύουν και για characters και για σταθερού μεγέθους strings και για structs/records, μιας και δεν αφορούν αριθμούς όλα τα προβλήματα, αλλά δεν ήμουν σίγουρος αν θα πρόσφερε ή θα έμπλεκε τη συζήτηση.