Ευχαριστώ για τις απαντήσεις σας!
Ο πρώτος αλγόριθμος, σε καμιά περίπτωση δεν είναι Ο(n^2).
Διαισθητικά συμφωνώ μαζί σου apoldem, αφού υπάρχει ισοδύναμος γραμμικός αλγόριθμος, θα πρέπει κι αυτός να θεωρείται O(n).
Όμως κι ο evry παραπάνω με είχε πείσει ότι έχουν την ίδια πολυπλοκότητα n
2 με την έννοια ότι:
σ' αυτό το στιγμιότυπο του προβλήματος έχουμε 10 δεκάδες, σ' ένα άλλο 100 εκατοντάδες και γενικά σε κάποιο άλλο Ν Ν-άδες
Άρα ο ένας αλγόριθμος θα το λύσει με 2 εμφωλευμένες δομές που θα κάνουν Ν επαναλήψεις η καθεμιά - άρα Ν*Ν
ενώ ο άλλος θα το λύσει γραμμικά με μία δομή που θα κάνει Μ επαναλήψεις, όπου Μ=Ν*Ν
Οπότε είναι και οι δύο Ο(Ν
2)
Έτσι, δεν ξέρω με ποια εξήγηση να πάω....
Δεν αρκεί να έχεις φωλιασμένους βρόγχους για να γίνει η πολυπλοκότητα τετραγωνική.
Σωστό μου ακούγεται και αναρωτιέμαι.... αλήθεια, τι αρκεί ?? (χάριν της θεωρητικής τεκμηρίωσης)
Ακόμα, αν καταλαβαίνω σωστά τη λογική που περιγράφεις και τη χρησιμοποιήσω παρακάτω, μπορώ να αποδείξω ότι η φυσαλίδα είναι Ο(Ν) !!!
Ας πάρω την "έκδοση" της φυσαλίδας που δίνει το τετράδιο του μαθητή στο παράδειγμα 3, σελ 49 (που είναι "λίγο χειρότερη" από τη γνωστή φυσαλίδα):
Για i από 1 μέχρι N-1 Για j από 1 από N-1 ...
| που γράφεται ισοδύναμα: | Για k από 1 μέχρι (Ν-1)^2 i ← (k-1) div (Ν-1) +1 j ← (k-1) mod (Ν-1) +1 ... |
Άρα με βάση τα προηγούμενα, δεν αρκεί το ότι η φυσαλίδα γίνεται με φωλιασμένες επαναλήψεις. Αφού μπορεί να γίνει και γραμμικά, είναι Ο(Ν)
(αλλά, βέβαια με ένα Ν που είναι ... της τάξης Ν
2 
)
Οπότε... πού καταλήγουμε ?