It seems the complexity of the following code should be O(n^2) but it's O(n), how?
void fun(int n, int arr[])
{
int i = 0, j = 0;
for(; i < n; ++i)
while(j < n && arr[i] < arr[j])
j++;
}
Asked
Active
Viewed 1.7k times
-1
ashish verma
- 23
- 1
- 1
- 6
-
Also, consider this code void fun(int n, int arr[]) { int i = 0, j = 0; for(; i < n; ++i) { j = 0; while(j < n && arr[i] < arr[j]) j++; } } – ashish verma May 06 '15 at 09:54
-
Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Dancrumb Aug 10 '17 at 15:35
6 Answers
4
In the first look, the time complexity seems to be O(n^2) due to two loops. But, please note that the variable j is not initialized for each value of variable i.
Hence, the inner j++ will be executed at most n times.
The i loop also runs n times.
So, the whole thing runs for O(n) times.
Please observe the difference between the function given in question and the below function:
void fun(int n, int arr[])
{
int i = 0, j = 0;
for(; i < n; ++i)
{
j = 0;
while(j < n && arr[i] < arr[j])
j++;
}
}`
Still not convinced ?
Let's assume the array passed has its element in decreasing order. We will just dry run through the code :
Iteration 1 : i = 0, j = 0. arr[0] < arr[0] is false. So, the
inner while loop breaks.
Iteration 2: i =1, j = 0. arr[1] < arr[0] is true. j becomes
Iteration 3 : i = 1, j = 1. Condition false. We break. Note
that j will remain 1 and is not reset back to 0.
Iteration 4 : i = 2, j = 1. arr[2] < arr[1]. True. j = 2.
Iteration 5 : i = 2, j = 2. Condition false. Break.
Iteration 6 : i = 3, j = 2. arr[3] < arr[2]. True. j = 3.
Iteration 7 : i = 3, j = 3. Condition false. Break.
As you can see, the inner while loop only runs once in this case. So, total iterations is 2 * N.
shobhit2905
- 87
- 6
2
j is not reset to 0 with every iteration of the outer loop. As such, it runs to n-1 just once, same as i does. So you have two parallel/intermingled iterations from 0 to (at most) n-1.
In every step, the program increases i by one. The program terminates when i reaches n. The "outer loop" is run n times.
There is also an "inner loop" about j. But all it does is increase j until it reaches i (at most, sometimes it does less). j is never decreased. So that part is also run at most n times in total (not n times for each iteration of the "outer loop").
Thilo
- 257,207
- 101
- 511
- 656
1
The answer is O(n) The outer loop runs 'n' times and the inner loop only runs to 'n' a single time in all the iterations combined as the value of j is never reset to 0. Therefore the answer is O(n+n)=O(n).
Sourabh Tomar
- 11
- 1
1
Lets consider the worst case when the while loop is executed maximum no. of times.
Initially: i=0 , j=0 => while loop does not gets executed since arr[0] = arr[0] i.e. j=0.
Second iteration : i=1 , j=0 => while loop gets executed for the worst case i.e. j=1.
Third iteration : i=2 , j=1 => while loop again gets executed for the worst case i.e. j=2.
...
nth iteration : i=n-1 , j=n-2 => while loop again gets executed for the worst case i.e. j=n-1.
So, by doing this exercise we can observe that every time j = i-1
except i=0 and j=0 OR we can say that the while loop is just running in parallel to the for loop and thus the no. of executions of the while loop is equal to the no. of executions of the for loop.
Hence Order = O(n);
FortyTwo
- 2,414
- 3
- 22
- 33
Gaurav Kumar
- 21
- 4
1
The answer is O(n) because the test condition inside the 'while' loop fails!
while(j < n && arr[i] < arr[j])
In the beginning, i=0 and j=0, which means arr[i] = arr[j], but the while loop test condition says arr[i]<arr[j], and its completely wrong to assume arr[0]<arr[0]
The code only runs the for loop n times.
The final answer is O(n) not O(n^2)
For some clarity, you can go through these two examples
Example 1 :
#include <stdio.h>
int main()
{
int i = 0, j = 0;
int n = 5;
int arr[] = {6,7,8,9,10,11};
for(; i < n; ++i)
{
printf("\nThis is for loop, its running 5 times\n");
while(j < n && arr[i] < arr[j]){
j++;
printf("\nThis is while loop!\n");
}
};
return 0;
}
The Output is :
This is for loop, its running 5 times
This is for loop, its running 5 times
This is for loop, its running 5 times
This is for loop, its running 5 times
This is for loop, its running 5 times
In the above output, we can't find the print statement present in 'while' loop
Example 2 :
#include <stdio.h>
int main()
{
int i = 0, j = 0;
int n = 5;
int arr[] = {6,7,8,9,10,11};
for(; i < n; ++i)
{
printf("\nThis is for loop, its running 5 times\n");
while(j < n && arr[i] <= arr[j]){
j++;
printf("\nThis is while loop!\n");
}
};
return 0;
}
Here, a small change is made
arr[i] <= arr[j]
'=' is used
Output:
This is for loop, its running 5 times
This is while loop!
This is while loop!
This is while loop!
This is while loop!
This is while loop!
This is for loop, its running 5 times
This is for loop, its running 5 times
This is for loop, its running 5 times
This is for loop, its running 5 times
Here, the print statement in while loop is executed, because arr[i]=arr[j],
arr[0] = arr[0]
For the 'Example 2' shown above the time complexity is O(n^2)
Fahaad Al Abbadi
- 11
- 2
1
Note that the variable j is not initialized for each value of variable i. Hence, the inner j++ will be executed at most n times. The i loop also runs n times. So, the whole thing runs for O(n) times.
Rohit Suryan
- 11
- 1