Question

Question 12: Please provide tilde (~) for the following expressions:

A) 300N + (3N^5) + (4N^5)*logN

B) (N)^(1/2) + 6 ( NlogN / logN^2 )

C) N^100/ 2^N

D) 1 + 1/N

Answer 1

Basics :

• For Finding Theta Notation First Find major term in each equation and ignore constant.
• Consider each statement for asymptotically large value of N

Answer (A)

F(N) = 300 N + (3 N⁵) + ( 4 N⁵) * logN  

F(N) = 300 N + (3 N⁵) + 4 N⁵ * logN // Major function is  N⁵ * logN

F(N) = 4 N⁵ * logN // ignore constant

F(N) = N⁵ * logN

F(N) = ( N⁵ * logN )

Answer(B)

F(N) = (N) ^(1/2) + 6 ( N logN / logN² )

F(N) = (N) ^(1/2) + 6 ( N logN / 2 x logN ) // Log Rule : logN² = 2 logN

F(N) = (N) ^(1/2) + 6 ( N logN / 2 x logN ) // cancel out logN

F(N) = N + 3 N    // Major function is  N

F(N) = 3 N    // ignore constant

F(N) = ( N)

Answer(C)

F(N) = N¹⁰⁰ / 2^N // For large value of N =1,2.3,4,,5...............∞

F(N) = N¹⁰⁰ / 2^∞

F(N) = N¹⁰⁰ / ∞ // (1 /   2^∞ ) = (1 / ∞) = 0 = constant time complexity

F(N) = 0

F(N) = (1) // Constant Time complexity is denoted by (1)

Answer(D)

F(N) =1 + 1/N     // For large value of N ie ∞

F(N) =1 + 1/∞

F(N) =1 + 0

F(N) =1

F(N) = (1)    // Constant Time complexity

Summary:

• Answer(A) F(N) = ( N⁵ * logN )
• Answer(B)   F(N) =   ( N)
• Answer(C)   F(N) = (1)
• Answer(D) ​​​​​​​   F(N) = (1)