Question

What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine?
B. Show that for any real constants a and b, where b > 0, (n + a)b = Θ(nb).
C. Show that the maximum degree of any node in an n-node binomial tree is lg n.

Answer 1

Explanation:

Brainly.in

What is your question?

1

Secondary School Computer science 5 points

“What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine?

Ask for details Follow Report by Npor 29.11.2017

Answers

jatin1896

jatin1896 Ambitious

100n^2<2^n

15 satisfies this.. :)

0.0

0 votes

THANKS

1

Comments (3) Report

how...Please explain

jatin1896

acc to question, 100n^2 should be less than 2^n, this is possible only with 15 and larger numbers.. try plotting the graph.. :)

send your Facebook account link

Log in to add a comment

sushma3patil Helping Hand

Answer: 15

Explanation:

For inputs of size n, running time of algorithm A is 100n2 and of B is 2n. For A to run faster than B, 100n2 must be smaller than 2n.

Calculate: A (quadratic time complexity) will run much faster than B (exponential time complexity) for very large values of n. Let’s start checking from n=1 and go up for values of n which are power of 2.

n=1⇒ 100×1^2 = 100 > 2^1

n=2⇒ 100×2^2 = 400 > 2^2

n=4⇒ 100×4^2 = 1600 > 2^4

n=8⇒ 100×8^2 = 6400 > 2^8

n=16⇒ 100×16^2 = 25600 < 2^16

Somewhere between 8 and 16, A starts to run faster than B. Let’s do what we were doing but now we are going to try middle value of the range, repeatedly (binary search).

n=8+16/ 2 = 12⇒100×12^2=14400 > 2^12

n=12+16/ 2=14⇒100×14^2=19600 > 2^14

n=14+16/ 2=15⇒100×15^2=22500 < 2^15

So, at n=15, A starts to run faster than B.