[Ar-Curunir]

AKS is not sublinear. It runs in poly(n) time, where n is the number of bits in the input (i.e. input size).