Hans Peterson wrote:I'm not sure in which Forum to post this question so I put it in Java in General.
Since this is not a Java question, I'll move it to our Computing forum.
The first (repeat) loop goes (in principle) n/log_2(n) times only that the rest in the division doesn't matter.
It doesn't. The repeat loop iterates
log₂(n) times, exactly as it says on line 8.
What division are you talking about? Why doesn't the rest matter? What rest?
So I'm looking here for a mathematical way to display only positiv integer. Maybe with the modulo function?
What positive integer? I thought you were looking for the Big Theta time complexity class.
The for loop runs exactly a times and therefore (imagine the result of the division is a positiv integer) has 2* n/log_2(n) calls.
It doesn't.
a = 2^log₂(n) = n. Again, what division?
For z I get the value z = n*(2j+1) because in the first step j=0 and z is n since z= 0 +0 +n = (j+1)*n.
Just because that's the answer in the first step doesn't make it the answer at the end of the loop.
The second loop runs
n times. Every step you add
j + n, where
j increments with each step. That means that at the end of the loop,
z = n² + 0 + 1 + ... + n-2 + n-1
= n² + n/2(n-1)
= 1½n² - ½n.
Now, the first loop runs in
Θ(log₂(n)) time and the second loop runs in
Θ(n) time. Because the second loop has a larger time complexity class, that one determines the time complexity of the function.
If instead of using loops, you calculate
z using the formula, the running time of the function will be in
Θ(1).