r/javahelp • • Jan 04 '19

Solved When is a loop o(1)?

I'm super confused about when a for loop/while loop is o(1).

For instance if I have an array A= {1,2,3,4,5};

for(int i = 0; i< A.length; i++){
//append to string or something
}

This loop would be O(n) ? I understand if I loop: for(int i = 0; i< 100; i++){ //append to string or something }

This is constant time but when else is a loop constant time?

16 Upvotes

8 comments sorted by

4

u/Holothuroid Jan 04 '19

Is this a Java question or more general?

In general there are some operations that at second glance can be simplified. Like adding numbers from 1 to n. It's n(n+1)/2 according to little Gauss.

4

u/[deleted] Jan 04 '19

Its a more general question relating to time complexity.

8

u/Alcool91 Jan 04 '19

In general a function is O(1) if the number of operations is constant with respect to its input. An example is a loop which always runs 5 times, computing the sum of the first five entries in an array. You can pass it an array as large as you want but the loop always runs 5 times. It does not scale with its input. 5 is always less than some constant multiple of 1 so we say it is O(1).

On the other hand, if you want to compute the sum of the every element in an array of n elements then you need to loop over the array and add each element to a running total, doing somewhere in the realm of n operations. If I pass in an array of 1000 elements then I have to do ~1000 operations whereas with the function above I still would only have to do 5 operations. Since in this case the number of operations we do scales linearly with the input we say it is O(n).

13

u/dkolion Jan 04 '19

Big O notation is a measure of complexity. A simplified way to look at it is how an algorithm grows/scales as a function of some input. In the first loop you provided, A is a parameter, with some length, which we call n. It stands to reason that as A grows, the running time of the loop will grow at the same rate. Because of this we say the loop is O(n), where n is the size of the array. In your second example, regardless of the size of the array (or any other input), we know that the loop will always run for exactly 100 iterations, in other words the runtime is constant with respect to the inputs, so it is O(1) complexity.

3

u/[deleted] Jan 04 '19

Yes, this loop will be O(n), where n = A.length. n is count of iterations in cycle.

3

u/sebnukem Jan 04 '19

A loop is O(1) when the number of loop is a constant independent of the size of the data you are working with.

2

u/rzwitserloot Jan 04 '19

What you're missing is that big-O notation is always relative to some input (and another aspect of big-O is what it measures: time (CPU complexity/how long does it take; assume RAM access is completely free and there is infinite ram), or space (how much memory will the algorithm take to do its job). If a big-O notation doesn't say, generally, time is intended).

Take this code: int sum = 0; for (int i = 0; i < A.length; i++) sum += A[i]; – if you say that the A variable is an input to this code, then this code's time complexity is O(n) with respect to A's size, which means: If you double the input's size, you'd approximately double the time complexity. It's space complexity is O(1); even if A is many millions of entries, this code doesn't take more RAM.

But here: int sum = 0; for (int i = 0; i < 1000; i++) sum += A[i % A.length]; - which is code that sums the first 1000 entries of A, looping back to the start if A is smaller than that, this code's time complexity is O(1) relative to A's size: It doesn't matter how large A is, the amount of steps this code would take is about the same. If you want to, you could say that it is O(n) relative to the 1000 constant written directly into the source code: If someone were to make that number 10 times as large, your code would take about 10x longer to run: That's O(n).

So, when is a loop O(1)? When the # of times it runs is not dependent whatsoever on the input size.

0

u/philipwhiuk Employed Java Developer Jan 04 '19 edited Jan 04 '19

If it does 1 thing per item, it's O(n).

If you want O(1) it can only do one thing no matter how many items exist.

"Reading the first element" is O(1) in a typical list.

"Reading an element" can either be O(1) for an array or O(n) for a linked list (because in the worst case you have to read each element to find the next all the way to the end of the list). For a heap it's O(n log n).

Something like sorting is not possible in O(n) because you have to do multiple comparisons between members of the list. Hence the best sort is O(n log n).