Please help!

2.  Let T(n) = ak * nk + ak-1 * nk-1 + ... + a1 * n + a0 . (ak, ak-1 ,..., a1, a0 are constants) 

Then T(n) = __________________? 
 O( n^(k^2) )
 O( n^(k-2 )
 O( n^2 )
 O( 2n )

 How to obtain the upperbound from this recurrence relation? I know the answer is O( n^(k^2) ) but I can't seem to remember how I got that answer.

4. Let T(n) = 3 * n  * log n + 2 * n . Which of the following statements is/are true? (Check all that apply)

 T(n) = O( n ^ 2)
 T(n) = Omega( n )
 T(n) = O( n )
 T(n) = Theta( n * log n) 

How to find the statements? I wasn't sure of how to start on this one. I know that using the Master Method isn't enough to find big-oh, big-omega, and theta as that only gives you big-oh.

7. Fill in the blank:        

?ni =1 ( i100 ) = T( __ )

In other words what is the T equivalent of 1100 + 2100 + 3100 + ... + n100 ?

Hint: Check out Faulhaber's formula. You may assume that the pattern in the examples continues indefinitely.

 n^99
 n^100
 n^101
 n^102
 n^100 * log n 

I know the answer is n^101 but I'm not sure how to prove it. I barely recall how that was done in my group.

rabbott wrote:

Re 2.  This isn't a recurrence relation. It's a timing function. (T does not appear on the right hand side.)  If the function is like this:

T(n) = a_k * n^k + a_k-1 * n^k-1 + ... + a₁ * n + a₀ 

the dominant term is a_k * n^k. You can ignore the rest of the terms (assuming a_k > 0)

Re 4. This isn't a recurrence relation either. Look at the dominant term.

Re 4 and 7. Don't worry about this for the final.

Yeah they aren't recurrence relations. I think I posted that question before having my previous ones answered.

Anyway, I understand now.