Theta function for (6n+1)(1+lg n)?

Clarification:
In your question:
(6n+1)(1+lg n)
the term in first bracket I can understand but what is the term in the
second bracket. Is it (1+g(n)) or something else.

Himanshu Arora

(6n+1)(1+lg n) = 6n + 6n lg n + 1 + lg n
The term of highest degree is 6n lg n. So it is sufficient to cancel
out constants and the other terms to get (6n + 1)(1 + lg n) = Theta (n
lg n).
If you need a formal proof, it is sufficient to show three constants
c1, c2 and n0, such that c1 n lg n <= |(6n + 1)(1 + lg n)| <= c2 n lg
n, for all n >= n0. Since lg is only valid for positive numbers, one
can present constants
 * c1 = 5
 * c2 = 7
 * n0 = any value so that 7n lg n >= 6n lg n + 6n + lg n + 1
     - see it's not necessary to consider n0 in terms of c1, since all terms
       are positive for n >= 1.

To calculate n0, one can use the fact that deriving the function
   f(n) = 7n lg n - (6n lg n + 6n + lg n + 1)
        = n lg n - 6n - lg n - 1

produces f'(n) = n + lg n - 6 - 1/n, which is positive for all n > 64.
It means that for all n > 64, f(n) is strictly crescent. Then, if you
can find an n0 such that f(n0) > 0, the problem is solved. The easiest
way to obtain this value without so many calculations is to get the
next power of 2: 128.

So, we can conclude that:
(6n + 1)(1 + lg n) = Theta (n lg n), since:
 5 n lg n <= (6n + 1)(1 + lg n) <= 7 n lg n, for all n >= 128.

[]'s
Tirelo.

Now I saw an element of your question that I had not devised before
answering it. The expression lg n means "logarithm of n in base 2",
i.e, lg n is a number y such that 2^y = n.

[]s Tirelo.