Time Complexity

Question

Which of the following statements is/are TRUE?
I. The time complexity of recurrence relation A(n) = 3A(n/2)+ n² is asymptotically faster than T(n) = 4T(n/2)+ n².

II. The time complexity of recurrence relation A(n) = 512 A(n/2) + O(n⁵⁰) is asymptotically faster than T(n) = 7T(n-53) + O(1), T(0) = 1.

Please explain what is mean by asymptotically faster?

Comments

1 is correct isn't it?

---

Asymptotically faster means that eventually it grows larger, but doesn't strictly mean that it's always going to be faster at the beginning....so i think both are wrong.

Answer 1

asymptotically faster means take less time for your first point A(n)=Big oh(n2) and T(n)=theta (n2logn)

Answer 2

I)  O(n^2) < O( n^2 log n)  so option is correct

II) O( 7 ^ n/53) < O(n ^50)  is correct but given is reverse

hence option 1 is correct

Comments

 O( 7 ^ n/53) > O(n ^50) 

you can check by taking log₇  both side. you will get n/53   >  50log₇n for large value of n, let n=7⁵⁰

7⁵⁰/53 > 50*50

Answer 3

Solution: Both the statements are true.

   Explanation: Here, Asymptotically faster means, time should be less but not more.

                       Statement-1:$ O(n^2)$ is lesser than$ O( n^2 log n). $So, statement-1 correct.

                        Statement-2: $O( 7 ^ n) $It is exponential. So, $O(n ^{50}) $is definitely lesser than $O( 7 ^ n)$

Comments

asymptotically faster means time taken by first one is less than second one .

Do you have any standerd reference for your above statement 

---

I have read it in clrs see this 

 

---

I can't understand, I have asked it, let's see anyone answers it