شما علامت O رو به معنای کوچکترمساوی (از لحاظ رشد) و علامت تتا رو دقیقا مساوی (از لحاظ رشد) بگیرید.
سوال اول شما:
بله می تونه باشه. n=O(n2)
سوال دوم شما:
مثالی رو می زنم:
فرض کنید f(n)=n2,g(n)=n
حالا داریم:
f(n)g(n)=n2n=f(n)O(f(n))
در این عبارت، تابع f با تابعی جمع شده که مرتبه آن کوچکتر یا مساوی مرتبه f می باشد. در نتیجه بدیهی است که حاصل این جمع، تابعی خواهد بود که مرتبه اش مساوی مرتبه f است. یعنی:
f(n)g(n)=n2n=f(n)O(f(n))=θ(f(n))=θ(n2)
خوب حالا شما می تونید در سمت راست عبارت به جای n2
توابعی با رشد بالاتر رو هم قرار بدید(البته با استفاده از علامت O به جای تتا ). مثلا
n2n=θ(n2),n2n=O(n2),n2n=O(n3),n2n=O(n4),...
اما معمولا ما به دنبال بهترین جواب هستیم که در تساوی فوق الذکر، استفاده از تتا بهترین، مناسب ترین و دقیقترین گزینه است.
توجه کنید که اگر مثلا تابع a برابر بیگ اوی تابع bباشه آنگاه لزوما برابر تتای آن نخواهد بود.
اما اگر مثلا تابع a برابر تتای تابع b باشه آنگاه برابر بیگ اوی b و نیز برابر بیگ اوی تمام توابعی که رشدشان بیشتر از b است، نیز خواهد بود.