First, you can eliminate the h of the algorithm to simplify a little more:
int Algoritmo(int A[], int n) {
int k=0, i=1, j=0;
while (i<n && k+j+1<n ) {
if (A[k+j] == A[(i+j)%n]) {
j = j+1;
}
else if (A[k+j] < A[(i+j)%n]) {
i = i+j+1;
j = 0;
}
else if (A[k+j] > A[(i+j)%n]) {
k = max(i, k+j+1);
i = k+1;
j = 0;
}
}
return k;
}
n seems to me to be the size of the array. Because the array is accessed at the following positions:
(i+j)%n which will give some position between 0 and n-1.k+j, but the condition of while ensures that k+j+1<n and that also means that k+j<n and so it’s something between 0 and n-2.
Within the while there are three conditions, comparing the A[k+j] with the A[(i+j)%n]. Either these two elements are equal, or the first is greater, or the second element is greater. Soon, there will always be one and only one of the conditions being true in every iteration of the while.
Let’s see how j evolves over time:
j=0; // Inicial
j = j+1; // Primeira situação (==)
j = 0; // Segunda situação (<)
j = 0; // Terceira situação (>)
That is to say, j starts at zero, increments from one to one every now and then or back to zero. To simplify the analysis, let us assume for now that the first condition (of the ==) will never be true and that therefore j would always be zero. We know this is not correct, but we will do it just to better understand what is going on in the algorithm. This way, it would look like this:
int AlgoritmoErrado(int A[], int n) {
int k=0, i=1;
while (i<n && k+1<n) {
if (A[k] < A[i%n]) {
i = i+1;
}
else if (A[k] > A[i%n]) {
k = max(i, k+1);
i = k+1;
}
}
return k;
}
Since by the definition of while, we have to i<n, we can eliminate the %n:
int AlgoritmoErrado(int A[], int n) {
int k=0, i=1;
while (i<n && k+1<n) {
if (A[k] < A[i]) {
i = i+1;
}
else if (A[k] > A[i]) {
k = max(i, k+1);
i = k+1;
}
}
return k;
}
Let’s see what this algorithm does. We know it only works when all array positions have different values (after all, we delete the case of == that would need the j to work).
We start with k=0 and i=1. The elements A[0] and A[1] are compared if the A[0] is smaller than the A[1], the i will be incremented, and then we will compare the A[0] with the A[2] and if the condition holds, we will compare the A[0] with the A[3]. That is, the condition of the < is maintained when the element A[k] is smaller than the elements that follow. If we have the case where the first element of the array is the smallest of all, zero will be returned by the algorithm, which seems to indicate that it discovers where the lowest value element is.
Let’s see what happens if we fall into condition >. We begin by comparing A[0] with A[1] and the smallest element is A[1]. So we compared A[1] with A[2], afterward A[2] with A[3], and the value of k is always the index value of the array with the smallest element.
We conclude that this algorithm returns the position in the array that has the lowest value found.
Knowing this behavior, we have that in this case where there is no j, the k will always be smaller (and never equal to) than i. So we can simplify the algorithm for the following:
int AlgoritmoErrado(int A[], int n) {
int k=0, i=1;
while (i<n && k+1<n) {
if (A[k] < A[i]) {
i = i+1;
}
else if (A[k] > A[i]) {
k = i;
i = k+1;
}
}
return k;
}
Which is equivalent to this:
int AlgoritmoErrado(int A[], int n) {
int k=0, i=1;
while (i<n && k+1<n) {
if (A[k] > A[i]) {
k = i;
}
i = i+1;
}
return k;
}
Since we always have to k<i, then the condition k+1<n is redundant because it will only be true if i<n also goes. So the algorithm looks like this:
int AlgoritmoErrado(int A[], int n) {
int k=0, i=1;
while (i<n) {
if (A[k] > A[i]) {
k = i;
}
i = i+1;
}
return k;
}
Which in turn is equivalent to this:
int AlgoritmoErrado(int A[], int n) {
int k=0;
for (int i = 1; i<n; i++) {
if (A[k] > A[i]) k = i;
}
return k;
}
And at this point it is already obvious that it will iterate exactly n-1 times, what would be Θ(n-1), but like the n dominates over the 1 we have Θ(n).
And as for the j? Did the j destroys the Θ(n) that the algorithm would be?
Elements are accessed at positions k+j and (i+j)%n. In the first condition, the k+j grows, approaching the end of the algorithm one step towards the condition k+j+1<n. In the third condition, the k increases and the j returns to zero, but the value of k+j also increases because k = max(i, k+j+1), which ensures that the new value of k+j shall be greater than or equal to k+j+1 previous. The k+j can only decrease in the second condition, but this reduction will only occur after a sequence of entries in the first condition, which will make the i increase in place by jumping over all positions k+j and approaching the end of the condition algorithm i<n while the k+j only goes back to the point before entry in the condition of == for the first time.
Thus it is concluded that at each iteration or a step closer to the stop condition k+j+1, or you step back a few steps from this condition, but you advance this same number of steps plus one towards the stopping condition i<n.
If to is the number of steps taken in the first and third situation approaching the stopping condition of the k+j+1 and b is the number of steps taken in the second situation approaching to reach the stop condition of the i<n, then at most a+b at least one of the conditions will be reached. Since we know that a<=n and b<=n then a+b<=2n.
This means that guaranteed in no more than 2n iterations the algorithm ends and in no less than n-1 iterations it ends. So the algorithm is Ω(n-1) and O(2n). How constant factors don’t matter and the n dominates over the 1, then Ω(n-1) is the same as Ω(n) and O(2n) is the same as O(n). And if the algorithm is Ω(n) and O(n) at the same time, so he is Θ(n).