[qopeq]

https://www.techiedelight.com/find-pair-with-given-sum-array/

Czy w trzecim rozwiązaniu to jest na pewno złożoność O(n)?
Przecież on tam używa find() które w najgorszym przypadku przeszuka i tak całą unordered_map?

#programowanie

[qopeq]

@qopeq: już nie ważne :) https://thispointer.com/what-is-hashing-and-hash-table/

[Hadzik]

@qopeq: oczekiwana złożoność przeszukiwania hashmapy to O(1)

[p.....u]

@qopeq: map to słownik, w którym użycie find zajmuje O(1) niezależnie ile znajduje się w nich par klucz wartość. W najgorszym wypadku pętla (nie na słowniku map ale na tablicy arr) wykona się n razy zatem złożoność wynosi O(n)

[qopeq]

@Hadzik @p0vnedu :dzięki