I ran and timed an implementation of the Weil pairing on three set of parameters. One with an order of 512 bits, one with 256 bits and the last with 161 bits.
I took the Miller's algorithm to compute the Weil pairing. The algorithm that I used for the multiplication of 2 points is the double-and-add. Both algorithms have a time complexity of $O(log (n))$ if I understood correctly.
The time I got was 10 seconds for 512 bits, 2,5 seconds for 256 bits and 1,1 seconds for 161 bits. When I see the time I got it seems more like a complexity of $O(n^2)$ or $O(n \cdot log (n))$.
Can someone tell me what the time complexity is based on my results?