Menu
I once understood this but not anymore. Lets say I have an algorithm that will return the number in the middle of an array.
for (int i = 0; i < nums.length; i++) {
if (i == nums.length / 2) return nums[i];
}
The worst case of this will always be O (n / 2) right? There is no worse case than this. But how come we just conclude that it is O(n) ?
368
Running time is how long it takes a program to run. Time complexity is a description of the asymptotic behavior of running time as input size tends to infinity. You can say that the running time "is" O(n^2) or whatever, because that's the idiomatic way to describe complexity classes and big-O notation.
O(N²) — Quadratic O(N²) represents the complexity of an algorithm, whose performance is proportional to the square of the size of the input elements. It is generally quite slow: If the input array has 1 element it will do 1 operation, if it has 10 elements it will do 100 operations, and so on.
So O(n) = O(2n). Neither is "faster" than the other in terms of asymptotic complexity. They represent the same growth rates - namely, the "linear" growth rate.
For any loop, we find out the runtime of the block inside them and multiply it by the number of times the program will repeat the loop. All loops that grow proportionally to the input size have a linear time complexity O(n) . If you loop through only half of the array, that's still O(n) .
Big O time complexity is not about measuring the actual time an algorithm will take, it instead specifies what variables the time complexity is dependent on and what kind of relationship there is between those variables and the time complexity (ie linear, polynomial, exponential, etc).
Because constants do not effect the type of function the time complexity is they do not change the Big O value.
Note in your case the code you wrote may actually compile to something with constant time if the compiler is smart enough to note all iterations of the loop are dead but one.
193
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
