How many times is x=x+1 executed in theta notation in terms of n?

Question

I'm taking Data Analysis and Algorithms in the Summer.

The question: Find a Θ-notation in terms of n for the number of times the statement x = x + 1 is executed.

for i = 1 to 526
    for j = 1 to n^2(lgn)^3
       for k = 1 to n 
           x=x+1

I'm confused on how to find the answer. The first line would be 526, then the second line is clearly n^2 times (lgn)^3, but would that be maybe 3(n^2)lgn? And then the third line is just n. So combined they would be 526*n^3(lgn)^3, and with just n it would be something like Θ(n^3)(lgn)^3. I'm not sure.

Also to make sure I understand this type of problem I have

for i = 1 to |nlgn| 
    for j = 1 to i
        x=x+1

The answer would be just nlgn because the i on the second line isn't important right?

Answer 1

Answering for the first part :-

for i = 1 to 526
for j = 1 to n^2(lgn)^3
   for k = 1 to n 
       x=x+1

This program will run 526 * n^2 * (lg n)^3 * n times = 526 * n^3 * (lg n)^3 times.

So, x = x +1 will be executed 526 * n^3 * (lg n)^3 times.

Coming to Big-theta notation,

As n is always greater than (lg n) for any n>1, so,

  c1 * n^3 <= 526 * n^3 * (lg n)^3 <= c2 * n^3 * (lg n)^3

for some positive constants c1<526 and c2>526, so the big-theta notation will be

θ(n^3*(lg n)^3).

Answering for the second part,

for i = 1 to |nlgn| 
for j = 1 to i
    x=x+1

Your assumption is quite incorrect. The inner-loop guided by j is also necessary for evaluation of x = x+1 statement as it is the body of the inner-loop which itself is a body of the outer-loop.

So, here, x = x + 1 will be evaluated for

= 1 + 2 + ... + n*(lg(n) times
= [n*lg(n) * {n*lg(n)}+1]/2 times.