Prima di tutto, sì: facendo due cose O (n) si ottiene un'altra operazione O (n). Termini costanti o addirittura fattori come "due" o anche "diciassette" non contano in questo calcolo.
In secondo luogo, beh, se davvero hai bisogno di confrontare ogni valore in entrambe le strutture, allora ovviamente non puoi fare di meglio che accedervi almeno una volta, quindi non c'è motivo di preoccuparsi di come ottenere una soluzione più veloce di quella.
Ma più in generale, qual è la soluzione migliore dipende da quali sono esattamente i requisiti. Devi scoprire se i due sono diversi, o come sono diversi, oppure devi anche scrivere uno dei due renderli uguali?
Scoprire se i due sono diversi significa che puoi fermarti una volta trovata la prima differenza. È ancora un'operazione O (n), ma potrebbe comunque risparmiare un tempo considerevole. Se devi compilare un elenco di differenze, ovviamente non puoi prendere quella scorciatoia. E se devi scrivere un file, allora probabilmente ci vorrà molto più tempo di qualunque operazione tu possa programmare sul contenuto (l'I / O del disco è tremendamente più lento della memoria operazioni), quindi probabilmente stai meglio semplicemente copiando un file con l'altro. (In effetti, la maggior parte dei file system solo ti consente di scrivere un intero file, quindi dovresti comunque pagare l'intera scrittura, anche se hai un elenco di differenze specifiche da elaborare.)