Algo HW #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)\)

\(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)\)

\(f(n)=lg(lg^*n), g(n)=lg^*(lgn)\)

\(f=O(g)\)

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

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

\(f(n)=2^n, g(n)=n^{lgn}\)

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

\(f=\Omega(g)\)

\(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)\)

\(f(n)=e^{cos(n)}, g(n)=lgn\)

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

\(f= O(g)\)

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

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

\(f=O(g)\)

\(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)\)

\(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)\)

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)\)

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})\]

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.

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

## Share on Social Media