UGC-NET | UGC-NET CS 2015年6月–III |问题35

设f（n）和g（n）是渐近非负函数。以下哪项是正确的？ （A） θ（f（n）*g（n））=min（f（n），g（n）） （B） θ（f（n）*g（n））=max（f（n），g（n）） （C） θ（f（n）+g（n））=min（f（n），g（n）） （D） θ（f（n）+g（n））=max（f（n），g（n）） 答复: （D） 说明：

• 案例1： 当f（n）和g（n）都不是常数函数时——在这种情况下，max（f（n），g（n））<=f（n）*g（n），因此max（f（n），g（n））不能提供f（n）*g（n）的上界。
• 案例2： 当f（n）和g（n）都是常数函数，或者当f（n）和g（n）中的任何一个是非零常数函数时，在这种情况下，f（n）*g（n）=θ（max（f（n），g（n）））。
• 案例3： 当f（n）和g（n）中至少有一个为0时，在这种情况下f（n）*g（n）！=θ（max（f（n），g（n）））。因为max（f（n），g（n））不能给出一个下限。

选项（D）是正确的。 这个问题的小测验