Introduction to
Logic Programming
What
versus
How
 

Exercise 5.3 - Analysis


For each of the queries shown below, select the expression that captures the worst case complexity of our standard evaluation algorithm without indexing. The symbol n represents the total number of objects in the domain.

goal(X,Y) :- p(X,Y) & q(Y) & q(Z)
n4 + n3 + n2 + n
2n4 + 2n3 + n2 + n
2n4 + 2n3
 
goal(X,Y) :- p(X,Y) & q(Y)
n4 + n3 + n2 + n
2n4 + 2n3 + n2 + n
2n4 + 2n3