با سلام
دوستان ممنون میشم بگید این رابطه درست است یا نه و چرا؟
[tex]2^{2n}= o(2^{n})[/tex]
با سپاس
درست نیست. چون عبارت سمت چپ برابر با ۴ به توان n هستش و رشد این تابع بیشتر از ۲ به توان n هستش نه کمتر
پ.ن: این نوع سوالات خیلی ساده هستن. بهتره خودتون بیشتر رو این سوالات فکر کنید.
این معادله بازگشتی رو که مربو میشه به مرتب سازی ادغامی چه طوری باید اثباتش کنیم ؟
t(n)= 2t(n/2)+(n-1
(راهنماییش هم اینه:
n=2^k فرض کنیم.و بعد از یه سری محاسبات به این برسیم:
t(n)=O(nlog
)