ROUGH DRAFT authorea.com/5039

# Problem 1

1. $$f(n)=\sqrt{2^{7n}}, g(n)=lg(7^{2n})$$

$$f(n)=2^{7n/2}, g(n)=2nlg(7)$$

$$f(n)=lg(2^{7n/2}), g(n)=lg(2nlg(7))$$

$$f(n)=lg(2^{7n/2}), g(n)=lg(2nlg(7))$$

$$f(n)=7n/2, g(n)=lg(2n) + lg(lg(7))$$

$$f(n)=7n/2, g(n)=lg(2n)$$

$$f=\Omega(g)$$

2. $$f(n)=2^{nln(n)}, g(n)=n!$$

$$f(n)=ln(2^{nln(n)}), g(n) = ln(n!)$$

$$f(n)=nln(n), g(n) = nlg(n)$$ (via previously proved identity)

$$f=\theta(g)$$

3. $$f(n)=lg(lg^*n), g(n)=lg^*(lgn)$$

$$f=O(g)$$

4. $$f(n)=\frac{lgn^2}{n},g(n)=lg^*n$$

$$f=O(g)$$ via limits. f approaches 0.

5. $$f(n)=2^n, g(n)=n^{lgn}$$

$$f(n)=n, g(n)=(lgn)^2$$

$$f=\Omega(g)$$

6. $$f(n)=2^{\sqrt{lgn}}, g(n)=n(lgn)^3$$

$$f(n)=(lgn)^{1/2} , g(n)=lg(n)+lg((lg(n))^3)$$

$$f=O(g)$$

7. $$f(n)=e^{cos(n)}, g(n)=lgn$$

$$f(n)=cos(n), g(n) = ln(lg(n))$$

$$f= O(g)$$

8. $$f(n)=lgn^2,g(n)=(lgn)^2$$

$$f(n)=2lg(n), g(n)=(lgn)^2$$

$$f=O(g)$$

9. $$f(n)=\sqrt{4n^2-12n+9}, g(n)=n^(\frac{3}{2})$$

$$f(n)=2n, g(n)=n^(\frac{3}{2})$$

$$f(n) = O(g)$$

10. $$f(n)=\sum_{k=1}^{n} k, g(n)=(n+2)^2$$

$$f(n) = \frac{k(k+1)}{2}$$ via summation formula $$g(n)=(n+2)^2$$

$$f=\theta(g)$$

# Problem 2

• Line 1: 1 - Constant

• Line 2: 1 (bitshifting)

• Line 3: 1

• Line 4: $$n^2$$ (modular arithmetic)

• Line 5: $$m$$ (loop)

• Line 6: $$n^3$$ (finding GCD)

• Line 8:lg(N)

• Line 9: $$n^3$$ (exponential modular arithmetic)

• Line 10: $$m$$ (loop)

• Line 11: $$n^3$$ (exponential modular arithmetic)

• Line 12: $$n^2$$ (modular arithmetic)

• Line 13: $$n^3$$ (primality test)

Total:

$$[(2n^3+n^2)m + n^3 + log(N) + n^3]m + n^2$$

$$m^2(n^3)$$

# Problem 3

• The lower bound for the height of the tree is 0, because the tree can consist of only the root node.

• The asymptopic behavior of $$h_{m}$$ relative to $$h_{m'}$$ depends on the relationship between m and m’ (whether one is larger than the other, or is equal).

$$N = \frac{1-m^{h+1}}{1-m}$$ via geometric sum

$$N(1-m) = 1-m^{h+1}$$

$$1 - N{1-m} = m^{h+1}$$

$$lg_{m}(Nm - N + 1) -1 = h$$

So looking at large values of N and M, this formula is basically

$$lg_{m}(Nm) = h$$ because $$Nm$$ is the dominating term. So if $$n=m^2$$, then the height of $$n$$ is double $$M$$.

$$lg(Nm) = h$$

Now if use $$n$$,

$$lg(Nn) = h$$

$$lg(N(m^2)) = h$$

$$lg(Nm) = \frac{h}{2}$$

So this shows, if you square m, it divides the height by 2.

• Using Master Thoerem, we will be able to write the recursive cost of this function as:

$T(n) = aT(\frac{n}{b}) + O(n^d)$

The branching factor $$a$$ is 1 because we are only left with one subproblem at each iteration. Also doing $$\frac{y}{2}$$ takes constant time because $$y$$ is in the order of $$2^n$$, so dividing by 2 is just a simple bitshift. The subproblem is $$n/2$$ because you only have to deal with a number with half the bitsize. THe cost of combining the subproblems back to the larger problem is the cost of squaring a number and then take mod on a number order $$2^0$$.

Squaring a number is like multiplying two $$n$$ bit numbers and using Gauss’ observation, it takes $$O(n^{1.59})$$ time. Taking mod on the order of $$2^o$$ is simple because you do a shift that takes constant time and the answer is the bits you were shifting. So the cost of recombining is $$O(n^{1.59})$$. So using Master Theorem:

$T(n) = 1*T(\frac{n}{2}) + O(n^{1.59})$

Using the theorem, lg(1) < 1.59 so cost of recursion is $$n^{1.59}$$, and we need to do recursion $$n$$ times. Since $$y=2^n$$, we need y = 1 until we can stop. So total time is:

$O(n^{2.59})$

# Problem 4

• Compute $$2^{902} mod 7$$

The stategy here is to look for a pattern for mod 7.

$$2^0 = 1 mod 7$$

$$2^1 = 2 mod 7$$

$$2^2 = 4 mod 7$$

$$2^3 = 1 mod 7$$

$$2^4 = 2 mod 7$$

$$2^5 = 4 mod 7$$

$$2^6 = 1 mod 7$$

$$2^7 = 2 mod 7$$

$$2^8 = 4 mod 7$$

We notice the pattern that every third power of 2 is congruet to $$1mod7$$, so we continued the pattern from $$2^{900}$$.

$$2^{900} = 1 mod 7$$

$$2^{901} = 2 mod 7$$

$$2^{902} = 4 mod 7$$

Now we know that $$2^{902} mod 7 = 4$$

• Multiplicative Inverse of:

$$11 mod 120: 11$$

$$13 mod 45: 7$$

$$35 mod 77: None$$

$$9 mod 11: 5$$

$$11 mod 1111: None$$

• The running time of an efficient algorithm for finding the inverses modulo $$x^m$$ is $$n^3$$ via the Extended Euclidean Algorithm.

# Problem 5

• It is true that the pairs $$(5x+3y,3x+2y)$$ and $$(x,y)$$ have the same GCD. Let’s first see how to find a relationship between $$a$$ and $$b$$ if we want to find the $$gcd(a,b)$$.

$gcd(a,b) = gcd(amodb,b)$

Let $$x = amodb$$, and let k be any number.

$x-a = bk$ $x=a+bk$

Let $$k=-1$$

$x=a-b$

Then, subsitute x back:

$gcd(a,b) = gcd(a-b,b)$

$gcd(5x+3y,3x+2y) = gcd(2x+y,3x+2y)$

$gcd(2x+y,3x+2y) = gcd(x+y,2x+y)$

$gcd(x+y,2x+y) = gcd(x,x+y)$

$gcd(x,x+y) = gcd(x,y)$

• Using the above reasoning for finding GCD, we ahve to pick a clever $$k$$ that is an integer and will ma