The paper submitted to VLDB [1] has a table (Table 1) which lists the time complexity for the PGM Index and compares it with a Sorted Array, a B-Tree and another type of Data Aware/Learned Index - FITing-tree

[1] http://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf