| Author |
Topic: Big O Notation |
|
Alex_Raj
member
offline  |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
 |
|
|
| Big O Notation |
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.
Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.
|
|
|
|
|
|
|
Alex_Raj
member
offline  |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
|
|
|
| Definition -- Big O |
Function f(x) is bounded above (upper-bounded) by function g(x) asymptotically, namely,
if and only if there exists a positive real number C and a real number x0 such that
|f(x)| <= C|g(x)| for all x>x0.
|
|
|
|
|
|
|
Alex_Raj
member
offline |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
|
|
|
| Definition -- Big Omega |
Function f(x) is bounded below (lower-bounded) by function g(x) asymptotically, namely,
if and only if there exists a positive real number C and a real number x0 such that
|f(x)| >= C|g(x)| for all x>x0.
|
|
|
|
|
|
|
Alex_Raj
member
offline |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
|
|
|
| Definition -- Big Theta |
Function f(x) is bounded both above and below (upper- and lower-bounded) by function g(x) asymptotically, namely,
if and only if there exists positive real numbers C1 and C2 and a real number x0 such that
C1|g(x)| <= f(x) <= C2|g(x)| for all x>x0.
|
|
|
|
|
|
|
Alex_Raj
member
offline |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
|
|
|
| Definition -- small o |
Function f(x) is bounded above (upper-bounded) by function g(x) asymptotically, namely,
for every positive real number C, there exists a real number x0 such that
|f(x)| <= C|g(x)| for all x>x0.
|
|
|
|
|
|
|
Alex_Raj
member
offline |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
|
|
|
| Definition -- small omega |
Function f(x) is bounded below (lower-bounded) by function g(x) asymptotically, namely,
for every positive real number C, there exists a real number x0 such that
|f(x)| >= C|g(x)| for all x>x0.
|
|
|
|
|
|
|
Alex_Raj
member
offline |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
|
|
|
| Big O Notation In Computer Science |
In Computer Science, Big O notation is used to describe the efficiency or complexity of an algorithm, specifically the execution time required or the space used by an algorithm. The measurement can be expressed as:
f(n) = O(g(n)) with n as the size of problem or input data.
Algorithm A: Count the number of data input
public static int count(int[] a){
return a.length;
}
Algorithm B: Count the number of data input
public static int count(int[] a){
int count = 0;
for(int i=0; i<a.length; i++){
count++;
}
return count;
}
As we can see, the execution time of algorithm B is proportional to the size of array: the more the size, the more the time consumed; whereas the execution time of algorithm A is irrelevant to the size of array and remains constant. Therefore, we can conclude:
Algorithm A = O(1)
Algorithm B = O(n)
Algorithm A is more efficient than B
|
|
|
|
|
|
|
Email To Friend | 
Set Alert To This Topic
New Topic | 
Post Reply 
posted on: 12/14/2013 09:28:33 PM
Edit
Quote
Report
Profile
Reply