I have an algorithm that I think its complexity is O(n^2). However, our teacher insists that the algorithm takes O(n) time. How can it be? Here is the pseudo-code of the algorithm:
// A is the input array.
// |A| is the size of the input array.
i = 1
j = 1
m = 0
c = 0
while i < |A| {
if A[i] == A[j]
c = c + 1
j = j + 1
if j > |A|
if c > m
m = c
c = 0
i = i + 1
j = i
}
return m