Take the 2-minute tour ×  Suppose I have a table with n records
in MySQL, what would be the time complexity for searching a
record based on some criteria (say id = n-1)? Is it a linear
time complexity or it has a constant time complexity ? Thanks in
advance :)  share|improve this question add comment  2 Answers
up vote 1 down vote accepted  If you index the column, then the
records will be binary-tree sorted, so it will be very fast. I'm
not too familiar with all the optimizations, but theoretically
at the very least it would be O(log n).  You can create the
index with the create index MySQL command.  create index
id_index on MyTable (ID);  share|improve this answer add comment
Depends on what kind of index you got on id. But if id is an
integer, and n is a constant, then it can run in log(n) with an
index on id.  share|improve this answer add comment  Your Answer