# Complexity of the algorithm to find occurences of a given number in a given array

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

• Does your teacher claim this particular algorithm is O(n) (I agree with you that it is O(n^2), not O(n)), or that the problem can be solved in O(n) (if so, please clarify what problem exactly you are trying to solve). – user53923 Mar 29 '17 at 9:25
• @user53923 He claims that this algorithm is O(n). I don't get it too. He is a little bit novice I think because he has a lot of mistakes when teaching stuff. – Bora Mar 29 '17 at 9:34
• (Unless I misread something) the algorithm loops through all combinations of $i$ and $j$ with $i \leq j$ (and $i$ and $j$ between $1$ and $|A|$), resulting in $O(n^2)$ – user53923 Mar 29 '17 at 10:29
• @hopingGI_in_P Please look at the comment of user53923. Because my solution is the same. – Bora Mar 29 '17 at 10:52
• What, exactly is it that you want the algorithm to do? Because right now, it doesn't do what you claim it does. For one: where's the second input? What you claim it does can indeed be done in O(n), and is much simpler than this algorithm. – Jörg W Mittag Mar 30 '17 at 13:15

If we retain only the references to i and j, the code reduces to

i = 1
j = 1
while i < |A|
j = j + 1
if j > |A|
i = i + 1
j = i


This is equivalent to

for i in [1 |A|]
for j in [i |A|]


... which is gone through about ${|A|^2 \over 2}$ times. So it is $\Theta(n^2)$: both $O(n^2)$ and $\Omega(n^2)$.

The algorithm appears to be looking for the maximum number of replicates in the array. There are faster ways to do so. A good hash map has (average) constant time access/update. So you can count how many of each thing are in the array in $\Theta(n)$ time. You can then find the maximum in $\Theta(n)$ time too.

So the problem admits a $\Theta(n)$ solution, but what you have been offered isn't it.

• You'll need to show an $\Omega(n^2)$ bound as well. – Raphael Apr 29 '17 at 8:20
• @Raphael I've shown $\Omega$ as much as $O$, but I need to state it. Quite right. Thank you. I slipped into the false habit of using $O$ to express of the order of. – Thumbnail Apr 29 '17 at 17:00

Your algorithm finds multiple occurrences of all elements of the given array within itself which takes $O(n^2)$ time because $n$ elements are to be compared and each element needs $n-1$ comparisons.
But finding the multiple occurrences of a given number in an array will take only $O(n)$ time as we will have to compare only $1$ given number with $n$ elements of the given array i.e. $n$ times.