Query complexity can refer to one of the following notions in computer science:

• Query complexity in database theory, the complexity of evaluating a query on a database when measured as a function of the query size
• Query complexity, the number of queries needed to solve a computational problem for an input that can be accessed only through queries, such as an implicit graph
• Query complexity in the decision tree model, the number of queries needed to solve a computational problem by an algorithm that is restricted to take the form of a decision tree