I am given the following recurrence: My question is the following: I am trying t

Question

I am given the following recurrence:

My question is the following:

I am trying to prove big O for the the equation. My understanding is that to find big O you need to find a constant c to multiply the right hand part (c n lg n) by that makes it larger the the left hand part (c n lg n - n(c lg3 -1). My question is what happens to the constant value c on the left side of the equation. When, calculating a constant for the right, do we use that same constant c on the left side as well? Or do we need to get rid of it somehow.

Thanks.

Explanation / Answer

f(n) = O(g(n)) means there are positive constants c and k, such that 0 f(n) cg(n) for all n k.

Which means c and k can be anything. If we there exist atlest on c and K which satsifies 0 f(n) cg(n) then fn=O(g(n)).

For you equation

( c n logn - n ( clg 3-1) ) which is always lesser than (c n lg n)

(c n logn) -( n ( clg 3-1) ) <= c n lg n for all c

Our intension of Big O we need to find an upper bound of our equation

In your case

( c n lg n ) is always an upper bound of ( (c n log n) - ( n (c lg 3 -1) ))

that is why we are neglecting (n (c lg 3 -1)) in your case

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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