Let f(n) = n2Logn and g(n) = n (logn)10 be two positive functions of n

1.	Let f(n) = n2Logn and g(n) = n (logn)10 be two positive functions of n. Which of the following statements is correct?(A) f(n) = O(g(n)) and g(n) != O(f(n))(B) f(n) != O(g(n)) and g(n) = O(f(n))(C) f(n) = O(g(n)) but g(n) = O(f(n))(D) f(n) != O(g(n)) but g(n) != O(f(n))
Answer» Answer: (B) Explanation: Any constant power of Logn is asymptotically smaller than n. Proof: Given f(n) =n²Logn and g(n) = n (logn)¹⁰ In these type of questions, we suggest you to first cancel out the common factor in both the function. After removing these, we are left with f(n) = n and g(n) = (logn)⁹. Removing a factor of nlogn from both functions. Now n is very very large asymptotically as compared to any constant integral power of (logn) which we can verify by substituting very large value say 2¹⁰⁰. f(2¹⁰⁰) = 2¹⁰⁰ = 1030 and g(2¹⁰⁰) =100⁹ = 1018. Always remember to substitute very large values of n in order to compare both these functions. Otherwise you will arrive at wrong conclusions because if f(n) is asymptotically larger than g(n) that means after a particular value of n, f(n) will always be greater that g(n).

Let f(n) = n2Logn and g(n) = n (logn)10 be two positive functions of n. Which of the following statements is correct?(A) f(n) = O(g(n)) and g(n) != O(f(n))(B) f(n) != O(g(n)) and g(n) = O(f(n))(C) f(n) = O(g(n)) but g(n) = O(f(n))(D) f(n) != O(g(n)) but g(n) != O(f(n))

Answer» Answer: (B)
Explanation:

Any constant power of Logn is asymptotically smaller than n.

Proof:

Given f(n) =n²Logn and g(n) = n (logn)¹⁰
In these type of questions, we suggest you to first cancel out the common factor in both the function. After removing these, we are left with f(n) = n and g(n) = (logn)⁹. Removing a factor of nlogn from both functions.

Now n is very very large asymptotically as compared to any constant integral power of (logn) which we can verify by substituting very large value say 2¹⁰⁰.

f(2¹⁰⁰) = 2¹⁰⁰ = 1030 and g(2¹⁰⁰) =100⁹ = 1018.

Always remember to substitute very large values of n in order to compare both these functions. Otherwise you will arrive at wrong conclusions because if f(n) is asymptotically larger than g(n) that means after a particular value of n, f(n) will always be greater that g(n).

Let f(n) = n2Logn and g(n) = n (logn)10 be two positive functions of n. Which of the following statements is correct?(A) f(n) = O(g(n)) and g(n) != O(f(n))(B) f(n) != O(g(n)) and g(n) = O(f(n))(C) f(n) = O(g(n)) but g(n) = O(f(n))(D) f(n) != O(g(n)) but g(n) != O(f(n))

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment