Question

Question 4: For each of the following, find the dominant term(s) having the sharpest increase in n and give the time complexity using Big-O notation. Consider that we always have nem. Dominant0(.] Expression term 2n2log4n +30m2log100m 7(n+5)4nlogn20 30n5logn 3nlog10n (2n3(10m3)) +(n/2(n2)2/100

Answer 1

Find the dominant term and Time complexity:

Expression 2n2log4n +30m2log100m 7(n+5y*+nlogn20 30n logn+3n log1On (2n3(10m))+)100 Dominant Term 2n log4n 7(n+5) 30nPlogn (n/2(n2)? /100 O(n2logn) O(nt) O(n'logn) O(n6)

Description:

(1) 2n²log4n + 30m²log100m (consider n > m)

Simplifying above expression to find time complexity:

2n²log4n + 30m²log100m

= 2n²(log₁₀4 + log₁₀n) + 30m² (log₁₀100+ log₁₀m)

= 2n²log₁₀4 + 2n²log₁₀n +30m²log₁₀100+30m²log₁₀m

Since n>m Dominant term for expression 2n²log4n + 30m²log100m is 2n²​​​​​​​log4n

Time complexity: O(n²logn)

(2) 7(n+5)⁴ + nlogn²⁰

Simplifying above expression to find time complexity:

7(n+5)⁴ + nlogn²⁰

= 7(n⁴ +20n³ + 150n² + 500n +625) + 20nlogn

= (7n⁴ +140n³ + 1050n² + 3500n +4375) + 20nlogn

Dominant term for expression 7(n+5)⁴ + nlogn²⁰  is 7(n+5)⁴

Time complexity: O(n⁴)

(3) 30n⁵logn + 3n log¹⁰n

Simplifying above expression to find time complexity:

30n⁵logn + 3n log¹⁰n

= 30n⁵logn + 3n log₁₀n¹⁰

= 30n⁵logn + 30nlogn

Dominant term for expression 30n⁵logn + 3n log¹⁰n is 30n⁵logn

Time complexity: O(n⁵logn)

(4) (2n³(10m³)) + (n/2(n²))² /100 (consider n > m)

Simplifying above expression to find time complexity:

(2n³(10m³)) + (n/2(n²))² /100

= (2n³(10m³)) + ( (n/2)² (n²)² )/ 100

= 20n³ m³+ ((n² * n⁴ ) / 200

= 20n³ m³ + n⁶ / 200

Since n>m Dominant term for expression (2n³(10m³)) + (n/2(n²))² /100 is (n/2(n²))² /100

Time complexity: O(n⁶)