# Thread: What is the Computional Complexity of this ?

1. ## What is the Computional Complexity of this ?

I'm new to this forum so first i want to say warm "Hello" to everyone, and especially to those that will help me (if any)

I have nothing special or very complicated here, i just need to know what will be the computational complexity of the simple algorithm below.

I am almost certain it should be O(N^2), but I just need to make sure.

Code:
int SomeFunction( int VarX ){

int Result = 0;
int Count = 0;

for (int i = 0; i < VarX; i++){
for (int j = 0; j <= 0.7 * VarX; j++){
Result = i + log(j*j);
Count++;
}
}

return 0.3 * Result;
}

I'm new to this forum so first i want to say warm "Hello" to everyone, and especially to those that will help me (if any)

I have nothing special or very complicated here, i just need to know what will be the computational complexity of the simple algorithm below.

I am almost certain it should be O(N^2), but I just need to make sure.

Code:
int SomeFunction( int VarX ){

int Result = 0;
int Count = 0;

for (int i = 0; i < VarX; i++){
for (int j = 0; j <= 0.7 * VarX; j++){
Result = i + log(j*j);
Count++;
}
}

return 0.3 * Result;
}
Yes, the computational complexity is on the order of $\displaystyle N^2$, if $\displaystyle N$ is the argument of the function (which is called "VarX" in your code).

I guess you erased a few lines of your program before posting it, because otherwise it looks pretty strange: the "Result" is computed lots of times, but used only at the end, and the "Count" remains unused.

By the way, here's a tip to improve (a very little bit) the complexity: in your code, the product 0.7 * VarX will be computed a lot of times. You should for instance let Y=0.7 * VarX before the loops, and compare "j <= Y" instead of "j <= 0.7 * VarX". In this case, this won't substancially change the speed, but it may be significant sometimes.