Algorithm
The growth of function
Big-O Notation
Let f and g be functions from the set of integers or the set of real numbers to the
set of real numbers. We say that f (x) is O(g(x)) if there are constants C and k
such that
|f (x)| ≤ C|g(x)|
whenever x > k.
- [This is read as “f (x) is big-oh of g(x).”]
- Could be refer to as the upper bound of f(x)
- The growth of f(x) will be always less then the growth of g(x), for C and x>k
Show that f(x)=x^2 +2x+1 is O(x^2).
We observe that we can readily estimate the size of f (x) when x > 1 because x <
x2 and 1<x2 when x>1.
- 0≤ x^2 +2x+1 ≤ x^2 +2(x^2) +x^2
- x^2 +2x+1 ≤ 4 (x^2); C = 4; k=1 [means x>1]]
Alternatively, we can estimate the size of f (x) when x > 2.
When x > 2, we have 2x ≤ x^2 and 1 ≤ x^2.
Consequently, if x > 2, we have
0≤ x^2 +2x+1 ≤ x^2 +x^2 +x^2 =3x^2.
It follows that C = 3 and k = 2 are also witnesses to the relation f (x) is O(x2).
Show that 7(x^2) is O(x3).
To show that if there are constants C and k such that |f (x)| ≤ C|g(x)|
- Note that when x > 7, we have 7x^2 < x 3
- we can take C = 1 and k = 7
Show that n^2 is not O(n).
- To show that n2 is not O(n), we must show that no pair of witnesses C and k
exist such that n^2 ≤ Cn whenever n > k.
- use a proof by contradiction
- Suppose that there are constants C and k for which n2 ≤ Cn
- n≤C
- no matter what C and k are, the inequality n ≤ C cannot hold for all n with n >
k.
- This contradiction shows that n2 in not O(n).
shows that 7(x^2) is O(x^3). Is it also true that x^3 is O(7x^2)
- We will show that no such witnesses exist using a proof by contradiction.
- x3 ≤ C(7x2)
- x ≤ 7C
- no matter what C is, it is not the case that x ≤ 7C for all x > k no matter what k
is
- x3 is not O(7x2).
How can big-O notation be used to estimate the sum of the
first n positive integers?
- 1 + 2 + · · · + n ≤ n + n + · · · + n = n2.
- From this inequality it follows that 1 + 2 + 3 + · · · + n is O(n2), taking C = 1
and k = 1 as witnesses.
Big-Omega
Big-Theta Notation
Show that 3(x^2) + 8x (log x) is big-theta(x^2).
Because 0≤ 8x logx ≤ 8x2,
it follows that 3(x^2)+8x logx ≤ 11x2 for x>1.
Consequently, 3x2 + 8x log x is O(x2).
Clearly, x2 is big-omega(3x2 + 8x log x).
Consequently, 3x2 + 8x log x is big-theta(x2).
One useful fact is that the leading term of a polynomial determines its order. For
example,
- if f (x) = 3x5 + x4 + 17x3 + 2, then f (x) is of order x5.
An algorithm is a finite sequence of precise instructions for performing a
computation or for solving a problem.
Searching Algorithms
THE LINEAR SEARCH
THE BINARY SEARCH
To search for 19 in the list:
Step0: 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22
Step1: 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22
Step2: 12 13 15 16 18 19 20 22
Step3: 18 19 20 22
Step3: 18 19
THE BINARY SEARCH
Complexity of Algorithms
- it must always produce the correct answer.
- it should be efficient
- time complexity
- the time required to solve a problem of a particular size
- space complexity
- analysis of the computer memory
- The time complexity of an algorithm can be expressed in terms of the number
of operations used by the algorithm when the input has a particular size.
- Time complexity is described in terms of the number of operations required
instead of actual computer time
Average-case performance of the linear search algorithm
In the linear search algorithm, at each iteration:
- Check if i ≤ n → to see if we’ve reached the end of the list.
- Compare x with aᵢ. Position of x Comparisons Explanation
So there are 2 comparisons per iteration inside the loop.
i=1 3 (2×1 + 1)
i=2 5 (2×2 + 1)
Total comparisons when x is found at position i: (2i + 1)
i=3 7 (2×3 + 1)
… … …
i=n 2n + 1 (2×n + 1)
Average-case performance of the linear search algorithm
So the sequence of comparisons is: 3,5,7,…,(2n+1)
Average comparisons = [(2×1+1)+(2×2+1)+(2×3+1)+…+(2×n+1)] / n
= [2(1+2+3+…+n)+n] / n
= [2×(n)(n+1)+n] / n
=n+2
For linear search
Case # Comparisons Asymptotic Time
Best (found at 1st) 3 O(1)
Average (found halfway) ~n O(n)
Worst (not found) 2n + 2 O(n)
Binary search complexity analysis
- Compare x (the target) with the middle element.
- If they match → found.
- If x < middle → search the left half.
- If x > middle → search the right half.
- Repeat until one element is left or the list is empty.
Binary search complexity analysis
Reducing search space by half in every step:
n, n/2, (n/2)/2=n/4, (n/4)/2 =n/8, , …., 1
Total comparison: 2k+2
Linear Search vs Binary Search
Algorithm Comparisons (Worst Case) Time Complexity
Linear Search n O (n)
Binary Search 2 (log n) + 2 O (log n)
- What are the best-case scenarios for linear search and binary search?
- What are the time complexity of the best case scenarios for linear and binary search?
Bubble Sort
Intuition: is to move the highest number to the bottom at each pass
Bubble Sort
Intuition: is to move the highest number to the bottom at each pass
Bubble sort complexity analysis
Number of comparisons
● In the first pass: (n - 1) comparisons
● In the second pass: (n - 2) comparisons
● …
● In the last pass: 1 comparison
total comparisons = (n-1) + (n - 2) + (n - 3) + … + 1
= (n-1) ( n - 1 + 1) / 2
= n (n-1) / 2
= (n^2)/2 - n/2
= O(n^2)
Complexity of Matrix Multiplication