I'm trying to understand the performance of database indexes in terms of Big-O notation. Without knowing much about it, I would guess that:

• Querying on a primary key or unique index will give you a O(1) lookup time.
• Querying on a non-unique index will also give a O(1) time, albeit maybe the '1' is slower than for the unique index (?)
• Querying on a column without an index will give a O(N) lookup time (full table scan).

Is this generally correct ? Will querying on a primary key ever give worse performance than O(1) ? My specific concern is for SQLite, but I'd be interested in knowing to what extent this varies between different databases too.