Hi all,
I've written an algorithm in MATLAB that uses a while loop to calculate a sequence a(n) given inputs u and v:
Code:
while u ~= a(n)*v
t = u;
u = v;
v = t - a(n) * v;
n = n + 1;
a(n) = idivide(u, v, 'floor');
end
How would I go about estimating the complexity in terms of u and v? So far I've said that each iteration takes 9 operations (or 10 depending on idivide, but a constant nonetheless) so the algorithm is O(N) where N is the number of iterations, but I can't see how N depends on u and v, and I'm not even sure this is correct. I've also tried contour-plotting the running times, which is pretty, but it still just seems random.
If it helps, the code is used to produce partial quotients for the number u/v. Given the relationship to Euclid's algorithm, I'd expect something a little worse than O(n^2) for n-digit u and v?
Thanks in advance!