Wouldn’t the complexity of the ORDER BY RAND also vary dependent on the number of records in the database (which you didn’t change) by a lot more than the alternative method would vary by the number of records retrieved? ORDER BY RAND only has a O(1) time complexity because you didn’t change the number of records in the data.
Also the number of records in the database would be the one changing over time. The number of records that are required to be retrieved would usually be fixed. That would give this method the O(1) complexity when the number of records in the database is varying and the number of records to retrieve is static.