If an algorithm executes a statement, it is n/2 times, then how come O is equal to O(n). Because the video explains that it is because of the degree of a polynomial. Please explain.
for(int i =0;i<n;i=i+2){
sout(n) ---- This statemet can be print n/2 times
}
f(n) = n/2 then O(n)
In simple words, although the statement will be printed n/2 times, it still holds a linear relationship with n.
For n=10, it will print 5 times.
For n=50, it will print 25 times.
For n=100, it will print 50 times.
Notice the linear relationship. The factor 1/2 is just multiplied by n. It is a linear relationship and O(n) signifies a linear relation and doesn't care of the constant (which is 1/2 in this case). Even f(n) = n/3 would have been O(n).
Yes, as Aoerz already said, to understand your problem, you should understand what the O notation means.
In a math way:
O(f(n)) = {g(n) : ∃c>0 ∧ n0 ≥ 0 | g(n) ≤ c*f(n) ∀ n ≥ n0}
so g(n) ∈ O(f(n)) if g(n) ≤ c*f(n) (after a certain n0 and a constant c)
To put it in a easy way, think of n as a really big number. How much all the other factors matter? So what's the only main factor that really matter?
Example:
f(n) = n^3 + 300*n +5 --> f(n) ∈ O(n^3) (try it with n=100 and you'll see that is already enough)
