-1

Consider a while loop that goes on for the entire life of the program. You have a String arraylist and for every String in array, you will compare it with every object from the array.

I'm not sure if this part matters, but assuming each object has a .getString() method which you compare with the String in the arraylist. 

ArrayList<String> stringArray = new ArrayList<>()
stringArray.add("hello");  // 0th element
.
.
.
stringArray.add("bye"); // mth element

while(true){
    //assume that you HAVE to instantiate a new object array every loop
    Object[] objectArray = {new object(), .....new object() };
    for(Object i : objectArray){
       if stringArray.contains(i.getString())
          return true;
       }
    }

If i'm not mistaken this operation takes O(m*n) time? the string arrayList would have m number of elements and the object array would have an n number of elements. Does the time complexity also play a factor in cpu usage?

Am_I_Helpful
  • 18,735
  • 7
  • 49
  • 73
JOSH
  • 23
  • 4
  • 1
    This isn't valid Java, so I'd say that it takes as many CPU cycles for the compiler to figure out that `Array` doesn't exist anywhere. Or that `Object#getString` isn't a valid function, either. – Makoto Jul 15 '15 at 06:37
  • 1
    @makoto thank you so much for your valuable input and correcting my pseudo code instead of looking at the actual question. Really great community. – JOSH Jul 15 '15 at 06:39
  • I do apologize, but if you wanted to know the run time of an operation, it should be something that is either compilable or something that doesn't use concretely defined functions. My mind doesn't register this as pseudocode, as this is something that is definitely implementable. I do apologize if I've offended you, but would you consider either changing the syntax so that it's valid, or making it pseudocode instead? – Makoto Jul 15 '15 at 06:41

1 Answers1

3

If i'm not mistaken this operation takes O(m*n) time? the string arrayList would have m number of elements and the object array would have an n number of elements.

Yes, you're right in calculating the time complexity for the given scenario(talking about the for-loop part). The ArrayList.contains() method takes O(m) time in checking the presence of the element in the ArrayList for m elements in the ArrayList. Also, check this answer for a proof of the same.

And, as you have n elements in the Object Array, therefore the net time complexity is O(m*n).

NOTE :- If you'll consider the whole program(including the infinite while-loop), then it may turn infinite in the worst-case if none of the value in the ArrayList contains any of the Object Array values, then again in the next iteration of the while-loop, the same Object-Array will be instantiated. The same for-loop will have O(m*n) worst-case complexity and again the same story forever.

Does the time complexity also play a factor in cpu usage?

Time-complexity is an algorithmic analysis approach to give an idea about how does the program depend on the input parameters. So, actually as the number of elements increase, the time-complexity will always give a generalised notion like O(n) or O(log n), it won't give the exact CPU performance measure. It is used to give an estimate about how the input members of the program affects the execution of the program.

And, the actual CPU execution of program will obviously be greater for large number of elements even though the time complexity will be formally defined as same.

Like, the time complexity for binary-search would be O(log n), even if you increase the number of n. It gives you a rough estimate. If you'll actually run the program, several other factors like environment,case-scenario(best/worst), etc. will come into play.

Community
  • 1
  • 1
Am_I_Helpful
  • 18,735
  • 7
  • 49
  • 73
  • since this is an infinite loop, wouldn't it be the same as executing a loop which iterates over an infinite number of elements? meaning that the cpu usage would be abnormally high yes? – JOSH Jul 15 '15 at 06:49
  • @JOSH-No dear,both are totally different cases. Actually, after your for-loop finishes its task(`returning the value` OR `nothing found to return`), there's nothing else left in the infinite while-loop which will account for its complexity. See there is no body after the for-loop in the infinite while-loop, so the CPU will simply keep the program running.Though CPU resources will actually keep on getting consumed,but, that's entirely different from getting complexity notion of the code. – Am_I_Helpful Jul 15 '15 at 06:52
  • @JOSH-Oh, YES, SORRY, I missed that point. If it returns any value, then the while-loop will break out. If it doesn't, then,again in the next iteration, the same Object Array will be instantiated, again the same for-loop will take place, and again the same story. The same picture will keep on looping forever until a user intervention takes place, OR outofmemory error occur. – Am_I_Helpful Jul 15 '15 at 07:23