# algorithm – Recurrence Relation for a loop – Education Career Blog

The question is to set up a recurrence relation to find the value given by the algorithm. The answer should be in teta() terms.

``````foo = 0;

for int i=1 to n do
for j=ceiling(sqrt(i)) to n do
for k=1 to ceiling(log(i+j)) do
foo++
``````

,

Not entirely sure but here goes.

Second loop executes `1 - sqrt(1) + 2 - sqrt(2) + ... + n - sqrt(n) = n(n+1)/2 - n^1.5` times => `O(n^2)` times. See here for a discussion that `sqrt(1) + ... + sqrt(n) = O(n^1.5)`.

We’ve established that the third loop will get fired `O(n^2)` times. So the algorithm is asymptotically equivalent to something like this:

``````for i = 1 to n do
for j = 1 to n do
for k = 1 to log(i+j) do
++foo
``````

This leads to the sum `log(1+1) + log(1+2) + ... + log(1+n) + ... + log(n+n)`. `log(1+1) + log(1+2) + ... + log(1+n) = log(2*3*...*(n+1)) = O(n log n)`. This gets multiplied by `n`, resulting in `O(n^2 log n)`.

So your algorithm is also `O(n^2 log n)`, and also `Theta(n^2 log n)` if I’m not mistaken.