Assume we are running the following query on a PostgteSQL table table1 with column col1 indexed via b-tree...
SELECT * FROM table1 WHERE col1='foo' ORDER BY col2;
Would the time complexity of the query be equal to...
O(log(n) + m*log(m))
given n is the number of rows in table1 and m is the number of rows satisfying the where clause?
Assuming an O(n log n) sorting algorithm is used...
If it does use the index, then yes, it's O(log n) to search the B-Tree and O(m log m) to order the rows.
However, databases are a case where the constants cannot be ignored. The constant on an index lookup is relatively high compared to a sequential scan. If most of the table matches col1='foo', Postgres might decide a full table scan, O(n), is faster than the index because of its lower constant. Then it's O(n + m log m).
In addition, the size of m will affect whether a file sort or in-memory sort can be used drastically effecting efficiency.
If the index is used for the condition, then the complexity would be
O(log(n) + m * log(m))
log(n) is for finding the first matching row, and m * log(m) is for sorting. There is an additional term m for reading m rows from the index, but m < m * log(m).
If you have an index on (col1,col2), you would get away without additional sorting, and the complexity would be reduced to
O(log(n) + m)