Πίνακας (δομή δεδομένων): Διαφορά μεταξύ των αναθεωρήσεων

Στην διπλανή εικόνα βλέπετε ένα παράδειγμα μονοδιάστατου πίνακα 6 θέσεων, του οποίου το πρώτο στοιχείο είναι το 4, το δεύτερο (όπως ακριβώς και το έκτο) είναι το 9, κ.ο.κ. Για να εντοπίσουμε ένα στοιχείο, αρκεί να το αναζητήσουμε με βάση τη θέση του. Παρόλο που αυτή η διαδικασία χρειάζεται σταθερό χρόνο (πολυπλοκότητα Ο(1)), η παρόμοια διαδικασία της αναζήτησης με βάση την τιμή (και όχι τη θέση) ενός στοιχείου απαιτεί γραμμικό χρόνο ως προς τον αριθμό των στοιχείων του πίνακα (πολυπλοκότητα Ο(Ν)). Για παράδειγμα, στον διπλανό πίνακα η εύρεση του στοιχείου "3" απαιτεί 4 βήματα, ενώ η εύρεση του στοιχείου "9" απαιτεί 6 βήματα, δηλαδή τη διάτρεξη ολόκληρου του πίνακα.