I asked the following question: I am given the following: 4T(n/2) + 100n I asked

Question

I asked the following question:

I am given the following:

4T(n/2) + 100n

I asked this before and got a good explanation of the recursion tree, but I have another question. Mainly, I am still trying to find the running time of 4T(n/2) + 100n for given input sizes. For example, if I am given big 0 n^2, I would get a constant, c, multiplied by input size and divided by operations per second. It would look like c * (input size)^2 / operations per second. My question is how do I know what value to use for the constant c.
Thanks.

I got the following answer:

so you can calculate c when you are give n^2+ 100n

and then

n^2+ 100n= O(n^2)

which means

n^2+ 100n<= c* n^2

c>= 1+100/n,

if we put initial value for n, i.e. n0=1

then

c>= 1+100, c= 101.

This is the minimum value required by c to hold the statement.

I understand the answer, but I have one question. In the first line it says you can calculate c when given n^2 + 100n

My question is how do you turn 4T(n/2) + 100n into n^2 + 100n to solve.

Thanks.

Explanation / Answer

Solution:

Since, 4T(n/2) is evaluated equivalent to n^2, that is why here it is considered, because to compare it needed to be in in generalized format.

if you are aware with the concepts master theorem then you must know that

for master theorem the expression shpuld be of this format

aT(n/b)+ f(n)

so, here a= 4, b=2

Now we will calculate n^(logb a)= n^(log2 4)= n^2

I hope your doubt is clear now, if not just ask in the comment section.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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