So I have most of these solved, but I could really use some help with a few of t

Question

So I have most of these solved, but I could really use some help with a few of the equations.

Stuck on the first three.

nlog3(n)+n = 10^6

n^n = 10^6

n! = 10^6 (stirlings approx)?

This one below I am pretty sure its right just need confirmation.

lglg n = log2(log2(n)

log2(log2(n) = 10^6 -> n = 4^(10^6)

Exercise 1: asymptotic behavior (20 points) 1. (10 points) Assume you have two computers, CA and CB, capable of performing 106 and 10 oper ations per second, respectively. Both computers run a set of algorithms whose precise complexities f(n) are given below. Determine the size n* of the biggest input that can be processed in 1 second for each computer, as in the example. n) | n' for Ca | n. for CB lg lg n Vn 14n +4 n log nn n2+7n n10 2n 3n n! 1012 1016 72

Explanation / Answer

solution:

given data :

computer A (c1) capability 10^6.

computer B (c2) capability 10^8.

lg lg n : C1 = 10^(10^(10^6)) , C2 = 10^(10^(10^8))

sqrt(n) : C1 = 10^12 , C2 = 10^16

14n+4 : C1 = (10^6 - 4)/14 = 71428 , C2 = (10^8 - 4)/14 = 7142856

n log3(n) + n : C1 = 88003 , C2 = 6542313

n^10 : C1 = 10^0.6 = 3 , C2 = 10^0.8 = 6

2^n : C1 = log2(10^6) = 19 , C2 = log2(10^8) = 26

3^n : C1 = log3(10^6) = 12 , C2 = log3(10^8) = 16

n! : C1 = 9 , C2 = 8

the size of n of the biggest input that cn be processed in 1 second for

computer A (C1) is 9.

the size of n of the biggest input that cn be processed in 1 second for

computer B (C2)is 8.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.