That certainly depends on the amount of computing power you can throw at it and what level of accuracy you are trying to achieve. But the most naive attempt using a Hough transformation will probably take a couple of milliseconds on your average computer. However, the accuracy will be far from good enough with such a simple approach.
I have no idea what amount of time state of the art algorithms will use, but I could well imagine that it is essentially a tunable parameter that is chosen to get the best accuracy given the amount of data you have to process and the time available to complete the task.
I have no idea what amount of time state of the art algorithms will use, but I could well imagine that it is essentially a tunable parameter that is chosen to get the best accuracy given the amount of data you have to process and the time available to complete the task.