1
$\begingroup$

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
| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – user53923 Mar 29 '17 at 9:25
  • $\begingroup$ @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. $\endgroup$ – Bora Mar 29 '17 at 9:34
  • $\begingroup$ (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)$ $\endgroup$ – user53923 Mar 29 '17 at 10:29
  • $\begingroup$ @hopingGI_in_P Please look at the comment of user53923. Because my solution is the same. $\endgroup$ – Bora Mar 29 '17 at 10:52
  • 2
    $\begingroup$ 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. $\endgroup$ – Jörg W Mittag Mar 30 '17 at 13:15
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You'll need to show an $\Omega(n^2)$ bound as well. $\endgroup$ – Raphael♦ Apr 29 '17 at 8:20
  • $\begingroup$ @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. $\endgroup$ – Thumbnail Apr 29 '17 at 17:00
0
$\begingroup$

Here's the heading of your question :

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

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.

I guess you are talking about the complexity of your algorithm(which does more work than needed) but the teacher is telling you about the complexity of going through the array and comparing each number in the array with the given number.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.