CODEWITHSUNDEEP
javaperformance
user1952556
user1952556

Reputation: 23

Time Complexity for the given code.

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;
}

Upvotes: 0

Views: 147

Answers (6)

World Gamer
World Gamer

Reputation: 333

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

Upvotes: 0

Leo
Leo

Reputation: 3143

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++)

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533432

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.

Upvotes: 3

NPE
NPE

Reputation: 500157

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.

Upvotes: 1

jlordo
jlordo

Reputation: 37813

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.

Upvotes: 1

Mike
Mike

Reputation: 2434

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.

Upvotes: 1

Related Questions