Recall the definition of Big Theta notation: A function f(n) is in Theta(g(n)) if there exist positive constants c1, c2, and n0 such that 0 ≤ c1·g(n) ≤ f(n) ≤ c2·g(n) for all n ≥ n0.

Compare the growth rates of n^1.001 and n log n. Since 1.001 > 1, n^1.001 grows asymptotically faster than n log n. This suggests that n^1.001 will dominate the sum n^1.001 + n log n.

To formally prove that n^1.001 + n log n = Theta(n^1.001), show that there exist constants c1, c2, and n0 such that c1·n^1.001 ≤ n^1.001 + n log n ≤ c2·n^1.001 for all n ≥ n0. Start by factoring out n^1.001 from the expression.