it's N^2 if the client is scanning through all the records. With N records and page size P, with p=N/P pages: the client does list?page=1 then list?page=2 ...

it's N^2 if the client is scanning through all the records. With N records and page size P, with p=N/P pages: the client does list?page=1 then list?page=2 ... list?page=p. the server then does scans P records for the first client request, 2P for the second up to pP=N. The total record scanned is (1+2+...N/P)P = (1+N/P)(N/P)1/2*P ~ O(N^2)