how to calculate the Time Complexity of GCD ,fibonacci,factorial Algorithm?

Answer 1

GCD: It depends what algorithm you are using, but if you are using Euclid's, it is O(lgn), where n is the larger (or the smaller) number. To see why notice that: GCD(a,b) = GCD(b,a mod b) = GCD(a mod b, b mod (a mod b)). Now since a mod b = r such that a = bq + r, it follows that r2r. So every two iterations, the larger number is reduced by a factor of 2 (at least) so there are at most O(lgn) iterations.

Fibonacci: It depends on how you calculate it. If you do so with a straightforward recursive algorithm, it will take O(F(n)) operations to calculate F(n), where F(n) is approximately 1.6^n. However if you calculate F(n) with a for loop, keeping track of the current and previous numbers, it can be done in O(n).

Factorial: yep, as the previous poster said it's O(n)

BUT: if you are doing multiplications with a fixed number of digits/bits, then Factorial will in practice be O(n^2) as will Fibonacci.

Answer 2

I'm assuming that this is really a computer science question.

The point is to figure out how many steps it will take to compute the answer for an arbitrary input N, and then express that in "big O" notation.

The factorial one is easy:

n! = n * n-1 * n-2 * ... * 1

How many multiplications is that? N. So this is O(N). I'll let you do the rest.