What is the worst time complexity of this algorithm?
void intFunction (int n, int value)
{
int b,c;
for (int j = 4; j < n; j++) {
for (int i = 0; i < j; i++) {
b *= val;
for (int k = 0; k < n; ++k)
c += b;
}
}
}
I just learned the concept of Big-O. so for this code, in my opinion, the execution time of the outer loop is n and the second inner one is n (n + 1) / 2 and the inner one is n (n + 1) / 2. so the running time will be O (N ^ 5)? I'm right?
source to share
Outer loop:
for (int j = 4; j < n; j++)
iterates n - 4
once, so it's O (n). Inner loop:
for (int i = 0; i < j; i++)
iterates at most n - 5
times, so this is also O(n)
. Innermost:
for (int k = 0; k < n; ++k)
iterates n
once, so it's O (n). The last difficulty O(n * n * n) = O(n^3)
.
source to share
Let's drop the number of iterations to get the time complexity information!
First cycle --->
for (int j = 4; j < n; j++){...} // it will iterate for n-4 times.
Second cycle --->
for (int i = 0; i < j; i++){...} //it'll iterate for j-1 times for each iteration of outer loop started by j. See,this is dependent on First Loop(the outermost loop)...
Third cycle --->
for (int k = 0; k < n; ++k){...} //it'll always run n times independent to any previous-iteration whenever it is executed
So the general iteration for the cases would be (in a simplified version): -
(n-4)*(j-1)*n times.
But j itself varies from 4 to n-1. So j depends on n. 4<=j<=n-1
i.e.., . // so here j will repeat n-5 times ...
The exact address would be:
n*n-5*n=n^3-5*n^2.
It is equal O(n^3)
.
So, when analyzing the worst case, the number of iterations will be n ^ 3-5 * n ^ 2 , and its time complexity will be O (n ^ 3) .
source to share