@Dave: Could you please correct me if am wrong here.
1) So we are looking out for the worst case, and that happens when m and n
are consecutive Fibo numbers, being mutually prime to reach other.
2) Its taking 5 iterations to reduce the number of digits in the smaller of
m and n, by one. Assuming
@Pralaybi: You've got it right. Since h is proportional to the log of the
smaller number, we also can say that the complexity is O(log^2 (smaller
number)).
Dave
On Friday, November 23, 2012 2:09:01 PM UTC-6, pralaybi...@gmail.com wrote:
@Dave: Could you please correct me if am wrong here.
@Bharat: See, e.g.,
http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency.
Dave
On Sunday, November 18, 2012 12:03:33 AM UTC-6, bharat wrote:
@ Dave : can u pls explain the solution u gave .
How can u say fibnocci sequence produces worst case ?
On Fri, Nov 16, 2012 at
Don, thanks for the solution, Can u pls explain how a+b gets reduced by
atleast 25%
On Fri, Nov 16, 2012 at 3:42 AM, Don dondod...@gmail.com wrote:
Tail recursion is no different than a loop, so the complexity is the
same as an iterative solution like this:
int gcd(int a, int b) // For ab
@ Dave : can u pls explain the solution u gave .
How can u say fibnocci sequence produces worst case ?
On Fri, Nov 16, 2012 at 11:15 AM, Shruti Gupta fundooshr...@gmail.comwrote:
Don, thanks for the solution, Can u pls explain how a+b gets reduced by
atleast 25%
On Fri, Nov 16, 2012 at 3:42
@Don : how can u say that a+b reduces by atleast 25% ..
in each iteration b won't be changed in (a+b). b just shifted to a. a gets
changed to a%b. == a+b will become at max 2b-1 .. we can't deduce any
relation between a+b to 2b-1.
why do we need the % of reduction on (a+b) in each iteration ?
Sorry, I said that wrong. a+b is reduced by 25% over any TWO
iterations.
Look at these cases
2a = b : b % (a % b) a and 2*a = b, so b is decreased by at least
half, so a+b decreased by at least 25%
a b : b will become b-a, which is less than b/2, decreasing a+b
by at least 25%.
a==b :
you see, in each step of recursion, the number of digits in *n* is decrease
by one(at least in worst case), so the complexity you can decide.
On Tuesday, November 13, 2012 3:34:06 PM UTC+5:30, Shruti wrote:
hi
Can anyone help me find out the time complexity of recursive gcd algorithm
@Sonesh: Not so. The worst case for Euclid's algorithm is when the numbers
are consecutive Fibonacci numbers. So (89,55) -- (55,34) -- (34,21) --
(21,13) -- (13,8) -- (8,5), so it took 5 steps to reduce the number of
digits of the first number from 2 to 1. Asymptotically, the number of
digits
Tail recursion is no different than a loop, so the complexity is the
same as an iterative solution like this:
int gcd(int a, int b) // For ab
{
while(1)
{
int c = a % b;
if (!c) return b;
a = b;
b = c;
}
}
The complexity is log(a) + log(b) because
10 matches
Mail list logo
