CODEWITHSUNDEEP
sqlalgorithmsortingtime-complexity
Saad
Saad

Reputation: 1360

Time complexity of sorting a list in descending order.

I have a list of pair of variables along with their correlation value stored in a database.

var1  var2  corr

My algorithm involves sorting the list in descending order (based on correlation values) and then retrieving top k pairs.

What would be the time complexity of this algorithm? Does it depend on how I am sorting it? I am sorting the list with sql query using ORDER BY clause.

Upvotes: 1

Views: 6361

Answers (1)

Gordon Linoff
Gordon Linoff

Reputation: 1270493

SQL databases manage multiple-level memory -- basically data pages in memory and storage on disk. Traditional measures of complexity do not do a good job of capturing performance characteristics of SQL queries. For that, you need to understand the execution plan, underlying algorithms, and size of data relative to available resources.

My next reaction is: If you need to sort the data, then sort the data. What does time complexity have to do with it? That is, what other options do you have?

In general, the sorts implemented in databases are going to have O(n log(n)) complexity. However, the actual speed depends heavily on other factors. An index on the column reduces the complexity. Data that fits in memory goes faster. Data that fits on a single page is likely to be faster yet.

I am not sure what you mean by "Does it depend on how I am sorting it?". There is only one way to express ordering in SQL, using the order by clause, and it doesn't have many options. Ordering by asc versus desc should have no or minimal impact on performance.

Upvotes: 2

Related Questions