Okay so I understand how to find the upperbound and lowerbound and hence theta for some simple functions like 4n + 5nlgn + 6 but what I don't understand is how to do it for the following function
1 + 2 + ... + n
I understand to find the upperbound you do the following steps
1 + 2 + ... + n ≤ n + n + ... + n x n = n^2 for all n ≥ 1
I understand why we substitute n but where does the n x n come from? (I got this example out of my text book)
I want to know this so I can solve
n + 2n + 3n + ... + n^2
I believe I would do something like this
n + 2n + 3n + ... + n^2 ≤ n^2 + n^2 + n^2 + ... + n^2 x n^2 = n^4 for all n ≥ 1?
Or is it
n + 2n + 3n + ... + n^2 ≤ n^2 + 2n^2 + 3n^2 + ... + n^2 x n^2 = ??? for all n ≥ 1?
Also, is the upperbound n^4 or am I not on the right track at all?
Basically I'm just trying to figure out how to find the upperbound at the moment and then I will attempt to find the lowerbound. I've been puzzling over this for a while and would really appreciate it anyone could help.