Big O: A Review
Pat Morin
COMP2402/2002
Carleton University
Pat Morin COMP2402/2002
Big O: A Review
Big O: Definition
O(g (n)) = {f (n) : there exists positive constants c and n0
such that f (n) ≤ cg (n) for all n ≥ n0 }
Pat Morin COMP2402/2002
Big O: A Review
Big O: Definition
O(g (n)) = {f (n) : there exists positive constants c and n0
such that f (n) ≤ cg (n) for all n ≥ n0 }
I
Notice: O(g (n)) is a set of functions
Pat Morin COMP2402/2002
Big O: A Review
Big O: Definition
O(g (n)) = {f (n) : there exists positive constants c and n0
such that f (n) ≤ cg (n) for all n ≥ n0 }
I
Notice: O(g (n)) is a set of functions
I
When we say f (n) = O(g (n)) we really mean f (n) ∈ O(g (n))
Pat Morin COMP2402/2002
Big O: A Review
Big O: Definition
O(g (n)) = {f (n) : there exists positive constants c and n0
such that f (n) ≤ cg (n) for all n ≥ n0 }
I
Notice: O(g (n)) is a set of functions
I
I
When we say f (n) = O(g (n)) we really mean f (n) ∈ O(g (n))
E.g., n2 + 42n + 7 = O(n2 ) means:
I
The function f (n) = n2 + 42n + 7 is in the set O(n2 )
Pat Morin COMP2402/2002
Big O: A Review
n2 + 42n + 7 = O(n2 )
n2 + 42n + 7 ≤ 2n2 for all n ≥ 50
Pat Morin COMP2402/2002
Big O: A Review
Example
I
Prove n2 + 42n + 7 = O(n2 )
Pat Morin COMP2402/2002
Big O: A Review
Example
I
I
Prove n2 + 42n + 7 = O(n2 )
n2 + 42n + 7 ≤ n2 + 42n2 + 7n2
= 50n
Pat Morin COMP2402/2002
2
Big O: A Review
for n ≥ 1
Example
I
I
Prove n2 + 42n + 7 = O(n2 )
n2 + 42n + 7 ≤ n2 + 42n2 + 7n2
= 50n
I
2
So, n2 + 42n + 7 ≤ 50n2 for all n ≥ 1
Pat Morin COMP2402/2002
Big O: A Review
for n ≥ 1
Example
I
I
Prove n2 + 42n + 7 = O(n2 )
n2 + 42n + 7 ≤ n2 + 42n2 + 7n2
= 50n
2
I
So, n2 + 42n + 7 ≤ 50n2 for all n ≥ 1
I
n2 + 42n2 + 7n2 = O(n2 ) [ c = 50, n0 = 1 ]
Pat Morin COMP2402/2002
Big O: A Review
for n ≥ 1
Example
I
Prove 5n log2 n + 8n − 200 = O(n log2 n)
Pat Morin COMP2402/2002
Big O: A Review
Example
I
Prove 5n log2 n + 8n − 200 = O(n log2 n)
5n log2 n + 8n − 200 ≤ 5n log2 n + 8n
≤ 5n log2 n + 8n log2 n
≤ 13n log2 n
Pat Morin COMP2402/2002
Big O: A Review
for n ≥ 2 (log2 n ≥ 1)
Example
I
Prove 5n log2 n + 8n − 200 = O(n log2 n)
5n log2 n + 8n − 200 ≤ 5n log2 n + 8n
≤ 5n log2 n + 8n log2 n
≤ 13n log2 n
I
5n log2 n + 8n − 200 ≤ 13n log2 n for all n ≥ 2
Pat Morin COMP2402/2002
Big O: A Review
for n ≥ 2 (log2 n ≥ 1)
Example
I
Prove 5n log2 n + 8n − 200 = O(n log2 n)
5n log2 n + 8n − 200 ≤ 5n log2 n + 8n
≤ 5n log2 n + 8n log2 n
for n ≥ 2 (log2 n ≥ 1)
≤ 13n log2 n
I
5n log2 n + 8n − 200 ≤ 13n log2 n for all n ≥ 2
I
5n log2 n + 8n − 200 = O(n log2 n) [ c = 13, n0 = 2 ]
Pat Morin COMP2402/2002
Big O: A Review
Some common relations
I
I
O(nc1 ) ⊂ O(nc2 ) for any c1 < c2
For any constants a, b, c > 0,
O(a) ⊂ O(log n) ⊂ O(nb ) ⊂ O(c n )
Pat Morin COMP2402/2002
Big O: A Review
Some common relations
I
I
O(nc1 ) ⊂ O(nc2 ) for any c1 < c2
For any constants a, b, c > 0,
O(a) ⊂ O(log n) ⊂ O(nb ) ⊂ O(c n )
I
These make things faster
2 log2 n + 2 = O(log n)
n + 2 = O(n)
2n + 15n1/2 = O(n)
Pat Morin COMP2402/2002
Big O: A Review
Some common relations
I
I
O(nc1 ) ⊂ O(nc2 ) for any c1 < c2
For any constants a, b, c > 0,
O(a) ⊂ O(log n) ⊂ O(nb ) ⊂ O(c n )
I
These make things faster
2 log2 n + 2 = O(log n)
n + 2 = O(n)
2n + 15n1/2 = O(n)
I
We can multiply these to learn about other functions,
O(an) = O(n) ⊂ O(n log n) ⊂ O(n1+b ) ⊂ O(nc n )
Pat Morin COMP2402/2002
Big O: A Review
Some common relations
I
I
O(nc1 ) ⊂ O(nc2 ) for any c1 < c2
For any constants a, b, c > 0,
O(a) ⊂ O(log n) ⊂ O(nb ) ⊂ O(c n )
I
These make things faster
2 log2 n + 2 = O(log n)
n + 2 = O(n)
2n + 15n1/2 = O(n)
I
We can multiply these to learn about other functions,
O(an) = O(n) ⊂ O(n log n) ⊂ O(n1+b ) ⊂ O(nc n )
I
Examples: O(n1.5 ) ⊆ O(n1.5 log n)
Pat Morin COMP2402/2002
Big O: A Review
An indulgence
I
In this course, we have seen expressions like O(n − i)
I
I
Two argument function g (n, i) = n − i
For the purposes of this course, we will take O(g (n, i)) to be
O(g (n, i)) = {f (n, i) :
I
there exists positive constants c and n0
such that f (n, i) ≤ cg (n, i) for all n ≥ n0
and all valid arguments i}
For example (Lists) valid values of i are {0, . . . , n − 1} or
(sometimes) {0, . . . , n}
Pat Morin COMP2402/2002
Big O: A Review
Why Use big-O Notation?
I
Consider the following (simple) code:
for ( int i = 0; i < n ; i ++) {
a[i] = i;
}
Pat Morin COMP2402/2002
Big O: A Review
Why Use big-O Notation?
I
Consider the following (simple) code:
for ( int i = 0; i < n ; i ++) {
a[i] = i;
}
I
The running time is
Pat Morin COMP2402/2002
Big O: A Review
Why Use big-O Notation?
I
Consider the following (simple) code:
for ( int i = 0; i < n ; i ++) {
a[i] = i;
}
I
The running time is
I
1 assignment (int i = 0)
Pat Morin COMP2402/2002
Big O: A Review
Why Use big-O Notation?
I
Consider the following (simple) code:
for ( int i = 0; i < n ; i ++) {
a[i] = i;
}
I
The running time is
I
I
1 assignment (int i = 0)
n+1 comparisons (i < n)
Pat Morin COMP2402/2002
Big O: A Review
Why Use big-O Notation?
I
Consider the following (simple) code:
for ( int i = 0; i < n ; i ++) {
a[i] = i;
}
I
The running time is
I
I
I
1 assignment (int i = 0)
n+1 comparisons (i < n)
n increments (i++)
Pat Morin COMP2402/2002
Big O: A Review
Why Use big-O Notation?
I
Consider the following (simple) code:
for ( int i = 0; i < n ; i ++) {
a[i] = i;
}
I
The running time is
I
I
I
I
1 assignment (int i = 0)
n+1 comparisons (i < n)
n increments (i++)
n array offset calculations (a[i])
Pat Morin COMP2402/2002
Big O: A Review
Why Use big-O Notation?
I
Consider the following (simple) code:
for ( int i = 0; i < n ; i ++) {
a[i] = i;
}
I
The running time is
I
I
I
I
I
1 assignment (int i = 0)
n+1 comparisons (i < n)
n increments (i++)
n array offset calculations (a[i])
n indirect assignments (a[i] = i)
Pat Morin COMP2402/2002
Big O: A Review
Why Use big-O Notation?
I
Consider the following (simple) code:
for ( int i = 0; i < n ; i ++) {
a[i] = i;
}
I
The running time is
I
I
I
I
I
I
1 assignment (int i = 0)
n+1 comparisons (i < n)
n increments (i++)
n array offset calculations (a[i])
n indirect assignments (a[i] = i)
= a + b(n + 1) + cn + dn + en, where a, b, c, d, and e are
constants that depend on the machine running the code
Pat Morin COMP2402/2002
Big O: A Review
Why Use big-O Notation?
I
Consider the following (simple) code:
for ( int i = 0; i < n ; i ++) {
a[i] = i;
}
I
The running time is
I
I
I
I
I
I
I
1 assignment (int i = 0)
n+1 comparisons (i < n)
n increments (i++)
n array offset calculations (a[i])
n indirect assignments (a[i] = i)
= a + b(n + 1) + cn + dn + en, where a, b, c, d, and e are
constants that depend on the machine running the code
Easier just to say O(n) (constant-time) operations
Pat Morin COMP2402/2002
Big O: A Review

Nala Patient Chair

Spectroscopy of Single-Particle States in Oxygen Isotopes via (p, 2p

SEQUENCES AND nth TERM - Burton Borough School

情報科学序論

軽量ビーム AX