Time complexity for the following for Largest in array of unsorted numbers

Question

Can anyone help to analyze the time complexity of this can and please explain why. I'm comparing the array elements with each other with one being max. I'm not sure how to calculate the time complexity for this. Can anyone help me with this?

 class Largest
 {
     public static void main (String[] args) 
  {
    int array[] = {33,55,13,46,87,42,10,34};
    int max = array[0]; // Assume array[0] to be the max for time-being

    for( int i = 1; i < array.length; i++) // Iterate through the First Index and compare with max
    {
        if( max < array[i])
        {
            max = array[i];
        }
    }
    System.out.println("Largest is: "+ max);
 }
}

Possible duplicate of [this](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm). — bcsb1001, Sep 01 '15 at 14:52

James Wierzba · Answer 1 · 2015-09-01T14:54:39.670

1

It is O(n)

//loop n-1 times, O(n)
for( int i = 1; i < array.length; i++) // Iterate through the First Index and compare with max
{
    //one comparison operation, O(1)
    if( max < array[i])
    {
        //one assignment operation, O(1)
        max = array[i];
    }
}

You do 2 constant operations, n-1 times.

O(n) * [O(1) + O(1)] = O(n)

edited Sep 01 '15 at 14:54

answered Sep 01 '15 at 14:52

James Wierzba

16,176
14
79
120

can you please elaborate – veeresh charantimath Sep 01 '15 at 14:53
yes, it's pretty clear now. Are there any ways to improve this code – veeresh charantimath Sep 01 '15 at 14:56
why looping n-1 times gives O(n)? – veeresh charantimath Sep 01 '15 at 14:57
Depends. You can sort it, which costs you O(n * logn), which is a higher cost, but you only need to do it once, and then checking the max value is as easy as looking at the first element. – James Wierzba Sep 01 '15 at 14:57
See this article, scan to the part labeled O(n) https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ – James Wierzba Sep 01 '15 at 14:59

score 0 · Answer 2 · answered Sep 01 '15 at 14:51

0

You loop goes around n - 1 times so the complexity is O(n)

answered Sep 01 '15 at 14:51

Peter Lawrey

525,659
79
751
1,130

Time complexity for the following for Largest in array of unsorted numbers

2 Answers2