Time Complexity for the given code.

Question

Below code is to find how many times a number is shown in an array. For Example:

1,2,2,2,3,4,5,5,5,5 number 2 = 3 times number 5 = 4 times.

What is the time complexity in Java for the below code? What is the best way to solve this problem in respect to Time complexity?

public static void main(String[]args)
    {
        int[] data = {1,1,2,3,4,4,4,5,6,7,8,8,8,8};
        System.out.println(count(data,8));


    }


public static int count(int[] a, int x)
{
    int count=0;
    int index=0;
    while(index<a.length)
    {
        if(a[index]==x)
        {
            count++;
        }
        index++;

    }
    return count;
}

You're iterating over the entire array once, so I would guess it's O(N). — Blender
– Blender, Commented Jan 6, 2013 at 9:43
Please fix your notation. O(n) and o(n) are not the same thing. In some sense they're the opposites of each other. See en.wikipedia.org/wiki/Big_O_notation — NPE
– NPE, Commented Jan 6, 2013 at 9:46
I am looking at the example above the code: are you trying to find the number of occurrences of all duplicates in a sorted array? — jlordo
– jlordo, Commented Jan 6, 2013 at 9:50

Peter Lawrey · Accepted Answer · 2013-01-06 09:43:05Z

3

is it o(n) ,logN or else?

You look at every element once so it is O(n)

if it is o(n), can I can i do this task with LogN complicity?

Do a binary search with a low and high value searching for the value just less than the one you search for and just above. The difference between these two result will tell you how many there are. This is an O(Log N) search.

answered Jan 6, 2013 at 9:43

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

nullpotent Over a year ago

That would be N*log(N) then, if he needs to check for every element.

Peter Lawrey Over a year ago

@iccthedral correct. Technically I would say O(M * log N) where M is the range of numbers. You won't do this if you need to count all elements unless there was a large amount of duplication.

Mike · Accepted Answer · 2013-01-06 09:42:34Z

1

while(index<a.length)

This loop is run once per value in data. This is O(n). If you want to do this in O(log n) you will need a sorted array and a binary search. You have a sorted array, so you would just need to do a binary search.

answered Jan 6, 2013 at 9:42

Mike

2,4441 gold badge16 silver badges19 bronze badges

Comments

jlordo · Accepted Answer · 2013-01-06 09:42:43Z

1

The answer is O(n).

You loop through the array looking once at every index.

e.g. array size is 10 --> 10 comparisons, array size is 100 --> 100 comparisons and so on.

answered Jan 6, 2013 at 9:42

jlordo

37.9k7 gold badges63 silver badges84 bronze badges

Comments

NPE · Accepted Answer · 2013-01-06 09:42:46Z

1

You examine each element of the array, and therefore your code has O(n) time complexity.

To do it in O(log n) time, you have to exploit the fact that the array is sorted. This can be done with a variant of binary search. Since this looks like homework, I'll let you think about it for a bit before offering any more hints.

answered Jan 6, 2013 at 9:42

NPE

503k114 gold badges970 silver badges1k bronze badges

Comments

Leo · Accepted Answer · 2013-01-06 09:44:42Z

0

O(n) This code uses each element of the array.

while(index<a.length)

You can replace it on

for(int index = 0; index < a.length; i++)

answered Jan 6, 2013 at 9:44

Leo

3,1336 gold badges41 silver badges63 bronze badges

Comments

World Gamer · Accepted Answer · 2013-01-06 10:17:12Z

0

O(n).When the code iterates through each and every element of the array,its 0(n).

answered Jan 6, 2013 at 10:17

World Gamer

3331 gold badge4 silver badges20 bronze badges

Collectives™ on Stack Overflow

Time Complexity for the given code.

6 Answers 6

2 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related