Γιώργο δεν έχω διαβάσει το σχετικό κεφάλαιο του βιβλίου οπότε μόνο κάποιες γενικούρες θα πω, αν τυχόν βοηθήσουν...
Καταρχάς, όταν μελετάμε συναρτήσεις στα μαθηματικά, τις μελετάμε ανάλογα με τον βαθμό τους... πρωτοβάθμια: ax+b, δευτεροβάθμια: ax²+bx+c κλπ. Ο βαθμός είναι το σημαντικό και όχι τόσο η τιμή του a. Αν το δούμε σαν γραφικές παραστάσεις, τότε οι πρωτοβάθμιες είναι ευθείες και οι δευτεροβάθμιες καμπύλες, εντελώς διαφορετικά πράγματα.
Το ίδιο είναι και στην πολυπλοκότητα. Όταν ένα πρόβλημα έχει είσοδο 1 δις στοιχεία, μας ενδιαφέρει αν θα χρειαστούμε αριθμό επαναλήψεων της τάξης του n*1 δις στοιχείων (δηλαδή O(n)). Δεν είναι ιδιαίτερα σημαντικό το πόσο θα είναι το n, το σημαντικό είναι ότι η λύση του προβλήματος είναι γραμμική. Αντίθετα, αν θέλαμε n*n επαναλήψεις, τότε αλλάζει ριζικά η τάξη της λύσης, άλλο πράγμα να πεις "χρειάζομαι 5*δις επαναλήψεις" και άλλο "χρειάζομαι 1.000.000.000*δις επαναλήψεις".
Σίγουρα μια λύση που θέλει 0.5*n πράξεις είναι καλύτερη από μία που θέλει 10*n πράξεις αλλά δεν είναι και ιδιαίτερα σημαντική αυτή η διαφορά. Γι' αυτό και όλα αυτά τα λέμε O(n) χωρίς να μπαίνουμε σε λεπτομέρειες. Αν αυξάνεται η τάξη (δύναμη) της λύσης (π.χ. εμφωλευμένη επανάληψη) τότε είναι που η λύση είναι σημαντικά χειρότερη και αξίζει να επισημανθεί.