आपने ‘Good Algorithm’ के बारे में पढ़ा है कि जिसकी Time Complexity कम होती है वही Good Algorithm होता है | अगर अब आपको एक ही problem के 10 अल्गोरिथम दे दिए जाए तो आप कैसे पहचानेंगे कि कौन सा अल्गोरिथम कम time लेगा और कौन सा अल्गोरिथम ज्यादा time लेगा अगर अल्गोरिथम कि time complexity n variable के रूप में दी हुई है |

आसान लगता है ना, इन questions को solve करिए |

Que 1– For larger n, which grows faster log n or √n?

Ans – We take log n ≈ √n

हम दोनों तरफ log लेंगे

→ log (log n) ≈ log (√n)

→ log (log n) ≈ log (n^1/2)

→ log (log n) ≈ ½ log (n)

So, log (log n) < constant.log n

√n ज्यादा fast grow करेगा log n से, और आप इसको hidden trial rule से भी check कर सकते हैं

हम ये larger n के लिए देख रहे है। n = 16 पर log n भी 4 है और √n भी 4 है पर जब n > 16 होगा तब √n काफी fast grow करेगा log n से |

Que 2- For larger n, which grows faster n! or nⁿ?

Ans –

n! = n * (n-1) * (n-2) * (n-3) * … * 2 * 1  (upto n terms)

nⁿ = n * n * n * n * … * n (upto n terms)

जब n > 1 होगा, तब nⁿ fast grow करेगा n! से.

Asymptotic Analysis

हम चाहते हैं की हमने जो अल्गोरिथम choose की है वो सबसे कम time ले | इस problem में हमारे पास 7 तरह की अल्गोरिथम हैं और उनकी time complexity भी दी हुई है, बस आपको पहचानना है कि किसकी time complexity सबसे कम होगी और हम उसी अल्गोरिथम को अपने program में लगायंगे |

A5 की time complexity सबसे कम है (log n), तो हम इसी अल्गोरिथम को अपने program में लगायंगे |

एक बात और, आपको ऊपर दो questions दिए गए है, सबसे ज्यादा problem log n और √n को पहचानने में होती है या फिर nⁿ और n! को पहचानने में होती है | उसका answer मैने दे दिया है और अगर कोई भी problem हो तो आप एक sequence को याद कर सकते हैं |

For larger n, the growth of time complexity is

Log n < √n < n < n log n < n² < n³ < 2ⁿ < 3ⁿ < n! < nⁿ

Note – nⁿ वाला question कभी नहीं आयेगा क्यूंकि इसकी complexity maximum होती है | ये बिलकुल वैसा ही है जैसे में आपसे पूछूँ की आप कहाँ रहते हैं? तो आप answer दे की मैं इस पृथ्वी पर रहता हूँ | हर कोई पृथ्वी पर रहता है उसमे कोई नयी बात नहीं है ।