-1

I had to create a function for an assignment and I have no idea how to figure out the complexity of it. Could someone please explain the Big O notation of the following function and give a little explanation why (so I know next time). Thank you.

public static int findRange(int[] thisArray) {
        int range = 0, max = 0, min = 0;
        max = thisArray[0];
        min = thisArray[3];
        range = max - min;
        return range;
Zack Zalud
  • 1
  • 4
    This is `O(1)`. There is no loop. Everything happens in constant time. – Elliott Frisch Apr 13 '18 at 21:17
  • 1
    There is a good explanation of Big O here: [What is Big O](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – MarkA Apr 13 '18 at 21:19
  • 1
    Your code is `O(1)` as mentioned in other comments. What I would like to say is that the code seems incorrect. Not sure exactly what you need to do but you just seem to be returning the difference between the first and 4th element of the array. To find the min and max, you need to loop through the array and find the min and max. That would be `O(n)` in the best case. – clinomaniac Apr 13 '18 at 21:19
  • Thank you. I had a feeling that was it that or 0(n). The main function sorted the array, I took the first and last values as the min and max, then subtracted to find the range. Sorry for not clarifying. – Zack Zalud Apr 13 '18 at 21:19
  • First you define what `n` is, which is likely length of array here, then you ask yourself: Will code run slower if `n` gets bigger (think HUGE, like into the millions). Since answer is no, so it's _O(1)_. – Andreas Apr 13 '18 at 21:30

3 Answers3

1

Posting as answer cause a lot more information:

Your code is O(1) as mentioned in other comments. What I would like to say is that the code seems incorrect. Not sure exactly what you need to do but you just seem to be returning the difference between the first and 4th element of the array. To find the min and max, you need to loop through the array and find the min and max. That would be O(n) in the best case.

Since this is an assignment, I am not going to write the code but just a guideline on what you need to be doing.

  1. Initialize two variables for max and min and set them to lowest and highest possible value.
  2. Loop through the array and compare each element to see if its greater than max or less than min.
  3. When the loop is finished, max and min will have your actual max and min values.
  4. Use these variables to calculate and return range.

With this algorithm, you will be looping through the array once and will be O(n) since the number of iterations will increase as the length of the array increases.

clinomaniac
  • 2,200
  • 2
  • 17
  • 22
0

Array lookup is O(1) for Java. Since all you are doing is accessing elements of an array ( Which is O(1) for each ), and then performing a constant time calculation, the overall complexity is O(1).

chevybow
  • 9,959
  • 6
  • 24
  • 39
0

Line by Line:

   int range = 0, max = 0, min = 0;

Assigning values to simple datatypes takes some constant of time; this constant depends on the JVM and hardware, but is constant nonetheless. O(1)+O(1)+O(1)

max = thisArray[0];

Now this is where the trick is. Arrays are simple datatypes, and as such access time to any value within an array is also constant. O(1)

min = thisArray[3];

Once again, accessing the array. O(1)

range = max - min;

calculations on simple datatypes are performed in constant time. O(1)

   return range;

return statements are also constant. O(1)

The greatest term is O(1), and that is the answer. I should also mention that assignment operator also performs in constant time

A. Allen
  • 25
  • 5