Все зависит от запроса или, точнее, от плана запроса, который MySql в конечном итоге выберет для обработки запроса.
Кроме того, все зависит от того, что мы подразумеваем под 'n', в этих больших выражениях O. Например, если 'n' - это значение счетчика, которое в конечном итоге вернулось, и если это значение соответствует счетчику, произведенному запросом, который требует многократного сканирования нескольких таблиц, сложность может быть хуже, чем линейная.