4
Because
V
*
has time complexity
q
, this must happen after at most
q
(
|
x
|
)
steps.