CODEWITHSUNDEEP
javaalgorithmtimebig-o
kids
kids

Reputation: 57

O(n log n) Time Complexity Algorithm?

I created this algorithm to find the best trade between 3 numbers. It goes through the program and finds the best day to sell, buy, and profit from stock. I need to explain the algorithm used and how the time complexity is O(n log n) but I have a lot of trouble determining that. I was hoping someone could explain O(n log n) and relate it to the method I have.

Here's my method:

public static Trade bestTrade(int[] a) 
   {
      int lowest = a[0];
      int lowestIndex = 0;
      int highest = a[a.length - 1];
      int highestIndex = a.length - 1;
      int profit = 0;

      for(int i = 1; i < a.length; i++) 
      {
         if (a[i] < lowest && i < highestIndex) 
         {
            lowest = a[i];
            lowestIndex = i;
         }  
      }

      for(int i = a.length - 2; i >= 0; i--) 
      {
         if (a[i] > highest && i > lowestIndex) 
         {  
            highest = a[i];   
            highestIndex = i;
         }  
      }

      for(int i = 1; i < a.length; i++) 
      {
         if (a[i] < lowest && i < highestIndex) 
         {   
            lowest = a[i];   
            lowestIndex = i;
         }  
      }

      if (highestIndex > lowestIndex) 
      {
         profit = highest - lowest;
         return new Trade(lowestIndex, highestIndex, profit);
      }

      return new Trade(lowestIndex, highestIndex, profit);
   }

}

Upvotes: 2

Views: 1694

Answers (4)

AlexG
AlexG

Reputation: 31

O(n)

It is directly proportional to the number of a.length. Each time the for function is run, it runs through every day of data. If there were a method where the number of processes went up by more than the pure number (nested fors) then it could be O(n log n) or O(n^2). But in this case, it's pretty clearly just big O of n.

Upvotes: 1

happyHelper
happyHelper

Reputation: 119

Try finding the answer to this by yourself. It will help a lot in the future. Also this looks like a O(N) , I am not sure why you are convinced that it is O(NlogN).

This link might be useful, http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

Upvotes: 1

wvdz
wvdz

Reputation: 16641

The complexity is O(n), where n the length of array a.

You loop 3 times over a, so the running time is roughly 3n, so it is of the order n: O(n).

Upvotes: 1

Joshua Byer
Joshua Byer

Reputation: 519

This function is of O(n) which is superior to O(n log n) . In general you just look at the loops, since there is no nested loops and you only have loops which go through all elements of a The function is considered n.

Upvotes: 1

Related Questions