Q2. (a) If f(n)+g(m)-O(f(n)) and f(n)+ h(n) - (h(n), use the definition of big O

Question

Q2. (a) If f(n)+g(m)-O(f(n)) and f(n)+ h(n) - (h(n), use the definition of big O notation to prove that gn)+ hn)-O(h(n)). (b) Algorthms A1 and A2 are stated to have complexities O(n) and o(3) respectively. On 10 seconds. an input of size n = 10,000 both algorithms run in exactly the same time t How much time da you expect each algorithm to take on an input of size i, n=9,990 ii. n 30.000 n algorithm is said to have complexity (log(n)). On a trial run, in ten seconds it executes for an input of n 128. Suppose we want to let it run "overnight" (lets say the we supply? night is 8 hours long, i.e. 28,800 seconds), what input (i.e. approximate value of n) should

Explanation / Answer

a) For simplicity, consider
a = f(n)
b = g(n)
c = h(n)

Now according to f(n) is O(g(n)), we can say, in layman terms,
a <= b   .......... (1)
and
from f(n) is O(h(n)), we have
a <= c ............(2)

So, adding eq. (1) and (2), we get
a+a <= b+c

Coming to asymptotic analysis, It'll become

f(n) = O(g(n)+h(n))

b)

when one specifies the complexity class of an algorithm, the intention is for the bounds provided to be as tight as possible. This is what we should assume here, to make this problem well-defined.

So we will assume that the run times of the two algorithms are like this:

time1(n) ~= k1 · n3

time2(n) ~= k2 · 3n

Using the provided information we can find k1 and k2.

10 = time1(10000) = k1 · 100003 => k1 = 10 / 1012 = 10-11

10 = time2(10000) = k2 · 310000 => k2 = 10 / 310000

Using these values for k1 and k2 we can compute the time for any other n values, by substituting them in the formulas for time1(n) and time2(n).

c)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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