A B-tree index is an ordered structure. Looking up a key is a descent through the internal nodes — O(log n) — followed by a sequential walk along the linked leaf level for as long as the predicate holds — O(k), where k is the number of rows returned. Total: O(log n + k).

A sequential scan is O(n) whatever the predicate. To return one row out of a thousand it reads all thousand and discards 999.

seq scan     id BETWEEN 500 AND 500   →  1000 rows examined, 1 returned
index scan   id BETWEEN 500 AND 500   →     1 row  examined, 1 returned

"Rows examined" is not a figure of speech. It is the number the planner budgets, and the number EXPLAIN ANALYZE prints as rows on each node. This lesson prints it too, so the asymptotics stop being a claim you have to take on trust.