+- Hack Forums (https://hackforums.net)
+-- Forum: Tech (https://hackforums.net/forumdisplay.php?fid=444)
+--- Forum: Coding (https://hackforums.net/forumdisplay.php?fid=151)
+---- Forum: Coders Lounge (https://hackforums.net/forumdisplay.php?fid=5)
+---- Thread: [Help] Calculating time complexity O(n) (/showthread.php?tid=6293381)
Calculating time complexity O(n) - TomDH - Feb 28, 2025
Hey there, I’m preparing for a test with a friend
And we came across this question from an earlier test
Gemini and gpt give different answers
Would love some advice
I need to calculate the time complexity range of this code:
I think it’s n^3 c *( logc of n)
He thinks it’s n^4 logc of n
Code
int func(int n, int c){
int s=0, m=0;
for(int i=4; i<n*n; i++){
for(int j=5; j<c*i; j*=c){
if(j^(c*n-1)){
for(int k=0;k<c*n;k++)
m++;
break;
}
for(int k=0;k<c*n;k++)
s++;
}
}
return s>m? s:m;
}RE: Calculating time complexity O(n) - WhiteTV - Feb 28, 2025
I asked DeepSeek and got the following response:
"The time complexity of the given function is O(c n^3 log(n)).
Let's analyze the nested loops:
1. The outer loop runs from i=4 to i<n*n, giving approximately n² iterations.
2. The inner loop starts with j=5 and multiplies j by c in each iteration (j*=c), creating a logarithmic pattern. For each value of i, this loop runs approximately log_c(c*i) times, which equals 1 + log_c(i).
3. The third loop runs c*n times for each iteration of the inner loop where certain conditions are met.
When we combine these factors:
- Outer loop: O(n²)
- Inner loop: O(log_c(i)) where i ranges from 4 to n²
- Third loop: O(c*n) for each valid inner loop iteration
The total complexity is the sum over i from 4 to n² of (log_c(i) c n), which simplifies to O(c n³ log(n)).
This analysis accounts for all nested loops and their respective iteration patterns, with the dominant factor being the combination of the quadratic outer loop, logarithmic inner loop, and the linear third loop."
I hope that could be of help with the explanation!
RE: Calculating time complexity O(n) - TomDH - Mar 1, 2025
(Feb 28, 2025 03:46 PM)WhiteTV Wrote: I asked DeepSeek and got the following response:
"The time complexity of the given function is O(c n^3 log(n)).
Let's analyze the nested loops:
1. The outer loop runs from i=4 to i<n*n, giving approximately n² iterations.
2. The inner loop starts with j=5 and multiplies j by c in each iteration (j*=c), creating a logarithmic pattern. For each value of i, this loop runs approximately log_c(c*i) times, which equals 1 + log_c(i).
3. The third loop runs c*n times for each iteration of the inner loop where certain conditions are met.
When we combine these factors:
- Outer loop: O(n²)
- Inner loop: O(log_c(i)) where i ranges from 4 to n²
- Third loop: O(c*n) for each valid inner loop iteration
The total complexity is the sum over i from 4 to n² of (log_c(i) c n), which simplifies to O(c n³ log(n)).
This analysis accounts for all nested loops and their respective iteration patterns, with the dominant factor being the combination of the quadratic outer loop, logarithmic inner loop, and the linear third loop."
I hope that could be of help with the explanation!
Thank you! that is the result I got myself, but after researching a lot more it turns out the correct answer is actually n^3 c, as the XOR condition is this is always triggered and then the middle loop runs only 1 time because of the break.
so its n^2 n * c