Big-O notation : When will we have N^2 and such ?
I just ask if we add up the number of operations and sum up and take the highest exponent (Big-O),when does we have a parabole or higher exponent ?
If increasing the input size by 1 increases the number of operations by K*n+C. (K and C are any "fixed" number)
Take a non-symmetric function that takes a pair (i.e. two arguments). Evaluating every combination requires n² calls. Increasing n by one requires:
-Evaluating every pair (i, n+1) (i is [1, n]) = n evaluations.
-Evaluating every pair (n+1, i) (i is [1, n]) = n evaluations.
-Evaluating the pair (n+1, n+1) = 1 evaluations.
Thus, increasing input size from 'n' to 'n+1' increases the total amount of evaluations by 2n+1. Add to that the original n² evaluations and you get n²+2n+1 = (n+1)².
You can deduct the Big O notation either from highest n-exponent of the full amount of evaluations (n² in this case), or from the "tightest upper bound" of the increment (n<=2n+1<=n², thus n² in this case).
Take a non-symmetric function that takes a pair (i.e. two arguments). Evaluating every combination requires n² calls. Increasing n by one requires:
-Evaluating every pair (i, n+1) (i is [1, n]) = n evaluations.
-Evaluating every pair (n+1, i) (i is [1, n]) = n evaluations.
-Evaluating the pair (n+1, n+1) = 1 evaluations.
Thus, increasing input size from 'n' to 'n+1' increases the total amount of evaluations by 2n+1. Add to that the original n² evaluations and you get n²+2n+1 = (n+1)².
You can deduct the Big O notation either from highest n-exponent of the full amount of evaluations (n² in this case), or from the "tightest upper bound" of the increment (n<=2n+1<=n², thus n² in this case).
Topic archived. No new replies allowed.