English | Español

Try our Free Online Math Solver!

Online Math Solver












Please use this form if you would like
to have this math solver on your website,
free of charge.

Solutions to Math Homework 1

1 Problem 1

The algorithm will print GCD and LCM of X and Y .
To prove: GCD(X,Y) is given by while LCM(X,Y) is given by
Proof: Invariant for GCD computation are GCD(X, Y ) =
GCD(x, y). Verify both steps maintain this invariant using the number theory
result that GCD(x,y) = GCD(x-y,y) = GCD(x,y-x). At termination we have
= y and therefore GCD(x, y) = GCD(x, x) =

Invariant for LCM computation is uy +vx. Verify that both steps of algorithm
maintain uy+vx as invariant. Therefore from the initialization conditions when
algorithm terminates uy +vx = XY +XY . Now since x = y = GCD(X, Y ) we
get × GCD(X, Y ) = XY . Using the number theory result we know that
is the LCM.

2 Problem 2(0.1)

3 Problem 3(0.2)

The given function g(n) turns out to be a geometic series and it evaluates to

(a) When c < 1, lower bound on Equation 1 can be obtained by analyzing the
case when n = 0 which is 1. Similarly upper bound is obtained by analyzing
the case when n → ∞ which comes out to be . Since we got two constants
bounding Equation 1 g (n) is Ө(1)

(b) When c > 1 similar analysis will produce upper and lower bounds as cn
which makes g(n) as Ө(cn)

(c) When c = 1, the bound of Ө(n) is straight forward as each term of g(n)
evaluates to 1 and there are n terms.

4 Problem 4(0.3)

(a) Base case :
Hypothesis :
Induction :


(b) Using the generating function derivation shown in class Fibonacci numbers
can be represented as


where and Now choosing c as log ø we need to prove that
We use induction to prove that.
Base case :
Hypothesis :
Induction :
Using induction hypothesis
Therefore c is given as log ø

(c)Any number in between 0.5 and logø will suffice. Largest is logø .

5 Problem 5(1.31)

(a) N is an n-bit number. N! is given by 1.2.3...N.
Upper Bound : Assuming each number 1,2,3,...,N is represented by n bits, the
result of multiplying N n -bit number will give a number of N n bits where
N = 2n. Hence it is O(N*n)
Lower Bound : Since each number i (1, 2, ...,N) can be optimally represented
by log i bits , total number of bits in N! is given by which is log N!.
Using Sterling’s approximation or using a factor argument we know
which implies that total number of bits in N! is lower bounded by N log N. It
turns out to be Combining both we get ө(N*n)

(b) A simple iterative algorithm to solve the problem is given by:

Input : N
Output : N!
prod = 1
for i = 1 to N
prod = prod * i
return prod

Complexity analysis :We present a worst case bound. Assuming each of the
number 1,2,3,...,N are n-bit long each multiplication computes product of a
×n bit number with n bit number. Therefore total time taken by the for-loop
is given by(n × in) which turns out to be O(N2 × n2)

6 Problem 6(1.32)

Given numbers X and Y, apply Euclid algorithm (page 20) to compute GCD(X,Y).
Followed by that get LCM(X,Y) by GCD computation takes O(n3)
where n are the number of bits in X, Y. Final LCM computation takes O(n2).
Therefore the algorithm is bounded by O(n3).

Prev Next