Getting the private key from a public key is known as "the elliptic curve discrete logarithm problem".
There are several algorithms to solve this problem:
1) brute force attack (roughly p steps, you mean this method)
2) Pollard Rho (roughly sqrt(p) steps, based on birthday paradox)
3) Baby Step - Giant Step ( roughly sqrt(p) steps if you have enough memory space to store sqrt(p) points)
(p = number of points = number of private keys )
Take a look at:
http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/
http://www.cs.umd.edu/~gasarch/COURSES/198/Su14/baby.pdf
I used the Baby Step - Giant Step applied to a search space of 2^54 points --> 2^27 steps (more or less). It took about 18 seconds to retrieve the private key. Obviously if I had to search the private key in the entire search space of 2^256 points, I couldn't perform the 2^128 required steps (this is computationally infeasible).
If you don't believe me, pick a random 55 bit private key (below 0x0000000000000000000000000000000000000000000000000080000000000000), then generate a public key (you can use http://gobittest.appspot.com/Address), post the public key here --> I will retrieve your private key