You're saying that during sequential scans, the time it takes per row is O(n) where n is the number of columns? I find that hard to believe. Can anyone confirm / deny this?
The number of columns in PostgreSQL is limited to 250-1600 [1] since a tuple (a row) can't span more than one page of memory. Since O-notation talks about asymptotic behavior, it doesn't really apply here.
But yes, tables with more columns normally take more time to scan sequentially. The complete tuple is always loaded (excluding the data of TOAST [2] attributes), there is no way to only load one column. This is one of the reasons that column-oriented databases can be faster than row-oriented databases [3].
The time complexity for sequential scan takes O(r), because every row must be read once. Of course rows are made up of columns so you can also specify it as O(rc) where c is the average column length.
