Introduction to ALgorithmic Analysis
In this chapter, we will answer the following two questions
What does it mean to be an efficient algorithm? How can one tell that it is more efficient than other algorithms?
based on some easy-to-understand searching and sorting algorithms that we may have seen earlier.
1
Thursday, September 15, 11
Searching Problem
Assume A is an array with n elements A[1], A[2], A[n]. For a given element x, we must determine whether there is an index j; 1 j n, such that x = A[j] Two algorithms, among others, address this problem
Linear Search Binary Search
2
Thursday, September 15, 11
Linear Search Algorithm
Algorithm: LINEARSEARCH Input: array A[1..n] of n elements and an element x. Output: j if x = A[j], 1 j n, and 0 otherwise.
1. 2. 3. 4. 5. j 1 while (j < n) and (x A[j]) j j + 1 end while if x = A[j] then return j else return 0
3
Thursday, September 15, 11
Analyzing Linear Search
One way to measure efficiency is to count how many statements get executed before the algorithm terminates One should keep an eye, though, on statements that are executed repeatedly. What will be the number of element comparisons if
X first appears in the first element of A X first appears in the middle element of A X first appears in the last element of A X doesnt appear in A.
4
Thursday, September 15, 11
Binary Search
We can do better than linear search if we knew that the elements of A are sorted, say in nondecreasing order. The idea is that you can compare x to the middle element of A, say A[middle].
If x < A[middle] then you know that x cannot be an element from A[middle+1], A[middle+2], A[n]. Why? If x > A[middle] then you know that x cannot be an element from A[1], A[2], A[middle-1]. Why?
5
Thursday, September 15, 11
Binary Search Algorithm
Algorithm: BINARYSEARCH Input: An array A[1..n] of n elements sorted in nondecreasing order and an element x. Output: j if x = A[j], 1 j n, and 0 otherwise.
1. 2. 3. 4. 5. 6. 7. 8. low 1; high n; j 0 while (low high) and (j = 0) mid (low + high)/2 if x = A[mid] then j mid else if x < A[mid] then high mid - 1 else low mid + 1 end while return j
6
Thursday, September 15, 11
Worst Case Analysis of Binary
What to do: Find the maximum number of element comparisons How to do:
The number of element comparisons is equal to the number of iterations of the while loop in steps 2-7. HOW? How many elements of the input do we have in the
First iteration Second iteration Thrid iteration ith iteration
The last iteration occurs when the size of array = 1.
7
Thursday, September 15, 11
Theorem
The number of comparisons performed by Algorithm BINARYSEARCH on a sorted array of size n is at most
8
Thursday, September 15, 11
Merging Two Sorted Lists
Problem Description: Given two lists (arrays) that are sorted in non-decreasing order, we need to merge them into one list sorted in non-decreasing order. Example:
Input 3 7 9 12 1 2 4 13 14
Output
9
Thursday, September 15, 11
Merging Two Sorted Lists
Problem Description: Given two lists (arrays) that are sorted in non-decreasing order, we need to merge them into one list sorted in non-decreasing order. Example:
Input 3 7 9 12 1 2 4 13 14
Output 1
Thursday, September 15, 11
12 13 149
We will be interested in merging two subarrays. Input: A[1..n], p, q, r. Merge A[p..q] with A[q+1..r].
10
Thursday, September 15, 11
How to merge two subarrays?
B[1..6] (temp) A[1..3] A[4..6]
245
3 78
10
Thursday, September 15, 11
How to merge two subarrays?
B[1..6] (temp) A[1..3] A[4..6]
245 2 245
3 78 378
10
Thursday, September 15, 11
How to merge two subarrays?
B[1..6] (temp) A[1..3] A[4..6]
245 2 23 245 245
3 78 378 378
10
Thursday, September 15, 11
How to merge two subarrays?
B[1..6] (temp) A[1..3] A[4..6]
245 2 23 23 4 245 245 245
3 78 378 378 378
10
Thursday, September 15, 11
How to merge two subarrays?
B[1..6] (temp) A[1..3] A[4..6]
245 2 23 23 4 23 4 5 245 245 245 245
3 78 378 378 378 378
10
Thursday, September 15, 11
How to merge two subarrays?
B[1..6] (temp) A[1..3] A[4..6]
245 2 23 23 4 23 4 5 23 4 5 78
Thursday, September 15, 11
3 78 378 378 378 378 378
10
245 245 245 245 245
Algorithm MERGE
Algorithm: MERGE Input: An array A[1..m] of elements and three indices p, q and r, with 1 p q <r m, such that both the subarrays A[p..q] and A[q + 1..r] are sorted individually in nondecreasing order. Output: A[p..r] contains the result of merging the two subarrays A[p..q] and A[q + 1..r]. Comment: B[p..r] is an auxiliary array.
11
Thursday, September 15, 11
Algorithm MERGE (Cont.)
1. s p; t q + 1; k p merge A[p..q] 2. while s q and t r 3. if A[s] A[t] then 4. temp[k] A[s] 5. ss+1 6. else 7. temp[k] A[t] 8. tt+1 9. end if 10. k k + 1 11. end while 12. if (s = q + 1) then temp[k..r] A[t..r] 13. else temp[k..r] A[s..q] 14. end if 15. A[p..r] temp[p..r]
with A[q+1..r]
12
Thursday, September 15, 11
Analyzing MERGE
Assuming arrays A[p,q] and A[q+1,r], where p =1 and r =n,
n element assignments are needed to copy A to temp. n element assignments are needed to copy temp to A. The total number of element assignments is 2n. Hence, the time complexity is O(n).
13
Thursday, September 15, 11
Selection Sort
Algorithm: SELECTIONSORT Input: An array A[1..n] of n elements. Output: A[1..n] sorted in nondecreasing order. 1. for i 1 to n - 1 2. k i 3. for j i + 1 to n
{Find the index of the ith smallest element}
4. if A[j] < A[k] then k j 5. end for 6. if k i then interchange A[i] and A[k] 7. end for
14
Thursday, September 15, 11
Selection Sort Example
i k 5 2 9 8 4
15
Thursday, September 15, 11
Selection Sort Example
i 1 k 5 2 9 8 4
15
Thursday, September 15, 11
Selection Sort Example
i 1 k 2 5 2 9 8 4
15
Thursday, September 15, 11
Selection Sort Example
i 1 k 2 5 2 2 9 8 5 9 8 4 4
15
Thursday, September 15, 11
Selection Sort Example
i 1 2 k 2 5 2 2 9 8 5 9 8 4 4
15
Thursday, September 15, 11
Selection Sort Example
i 1 2 k 2 5 5 2 2 9 8 5 9 8 4 4
15
Thursday, September 15, 11
Selection Sort Example
i 1 2 k 2 5 5 2 2 2 9 8 5 9 8 4 9 8 4 4 5
15
Thursday, September 15, 11
Selection Sort Example
i 1 2 3
15
Thursday, September 15, 11
k 2 5
5 2 2
2 9 8 5 9 8 4 9 8
4 4 5
Selection Sort Example
i 1 2 3 k 2 5 5
15
Thursday, September 15, 11
5 2 2
2 9 8 5 9 8 4 9 8
4 4 5
Selection Sort Example
i 1 2 3 k 2 5 5 5 2 2 2 2 9 8 5 9 8 4 9 8 4 5 8 4 4 5 9
15
Thursday, September 15, 11
Selection Sort Example
i 1 2 3 4
Thursday, September 15, 11
k 2 5 5
5 2 2 2
2 9 8 5 9 8 4 9 8 4 5 8
4 4 5 9
15
Selection Sort Example
i 1 2 3 4 k 2 5 5 4 5 2 2 2 2 9 8 5 9 8 4 9 8 4 5 8 4 4 5 9
15
Thursday, September 15, 11
Selection Sort Example
i 1 2 3 4 k 2 5 5 4 5 2 2 2 2 2 9 8 5 9 8 4 9 8 4 5 8 4 5 8 4 4 5 9 9
15
Thursday, September 15, 11
Analyzing Selection Sort
Iteration 1 2 3 .. n-1
Total is
# of comparisons n-1 n-2 n-3 .. 1
Hence, time complexity is
16
Thursday, September 15, 11
Insertion Sort
Algorithm: INSERTIONSORT Input: An array A[1..n] of n elements. Output: A[1..n] sorted in nondecreasing order. 1. for i 2 to n 2. x A[i] 3. j i - 1 4. while (j > 0) and (A[j] > x) 5. A[j + 1] A[j] 6. j j - 1 7. end while 8. A[j + 1] x 9. end for
17
Thursday, September 15, 11
Insertion Sort Example
x=2 5 2 9 8 4
18
Thursday, September 15, 11
Insertion Sort Example
x=2 5 2 5 9 9 8 8 4 4
18
Thursday, September 15, 11
Insertion Sort Example
x=2 5 2 9 9 8 8 4 4
2 5
18
Thursday, September 15, 11
Insertion Sort Example
x=2 x=9 5 2 9 9 8 8 4 4
2 5
18
Thursday, September 15, 11
Insertion Sort Example
x=2 x=9 5 2 9 9 8 8 8 4 4 4
2 5
18
Thursday, September 15, 11
Insertion Sort Example
x=2 x=9 5 2 9 9 9 8 8 8 4 4 4
2 5 2 5
18
Thursday, September 15, 11
Insertion Sort Example
x=2 x=9 x=8 5 2 9 9 9 8 8 8 4 4 4
2 5 2 5
18
Thursday, September 15, 11
Insertion Sort Example
x=2 x=9 x=8 5 2 9 9 9 8 8 8 4 4 4 4
18
Thursday, September 15, 11
2 5 2 5
Insertion Sort Example
x=2 x=9 x=8 5 2 9 9 9 8 8 8 9 4 4 4 4
18
Thursday, September 15, 11
2 5 2 5
Insertion Sort Example
x=2 x=9 x=8 5 2 9 9 9 8 8 8 9 4 4 4 4
18
Thursday, September 15, 11
2 5 2 5 2 5
Insertion Sort Example
x=2 x=9 x=8 5 2 9 9 9 8 8 8 8 9 4 4 4 4
18
Thursday, September 15, 11
2 5 2 5 2 5
Insertion Sort Example
x=2 x=9 x=8 x=4 5 2 9 9 9 8 8 8 8 9 4 4 4 4
18
Thursday, September 15, 11
2 5 2 5 2 5
Insertion Sort Example
x=2 x=9 x=8 x=4 5 2 9 9 9 8 8 8 8 9 4 4 4 4
18
Thursday, September 15, 11
2 5 2 5 2 5
Insertion Sort Example
x=2 x=9 x=8 x=4 5 2 9 9 9 8 8 8 8 9 4 4 4 4 9
Thursday, September 15, 11
2 5 2 5 2 5
18
Insertion Sort Example
x=2 x=9 x=8 x=4 5 2 9 9 9 8 8 8 8 9 8
Thursday, September 15, 11
4 4 4 4 9
18
2 5 2 5 2 5
Insertion Sort Example
x=2 x=9 x=8 x=4 5 2 9 9 9 8 5
Thursday, September 15, 11
8 8 8 9 8
4 4 4 4 9
18
2 5 2 5 2 5
Insertion Sort Example
x=2 x=9 x=8 x=4 5 2 9 9 9 8 5 8 8 8 9 8 4 4 4 4 9
18
2 5 2 5 2 5 2
Thursday, September 15, 11
Insertion Sort Example
x=2 x=9 x=8 x=4 5 2 9 9 9 8 5 8 8 8 9 8 4 4 4 4 9
18
2 5 2 5 2 5 2 4
Thursday, September 15, 11
Analyzing Insertion Sort
The minimum number of element comparisons is n-1 which occurs when input is sorted The maximum number of element comparisons is which occurs when input is reversely sorted. Time complexity is
19
Thursday, September 15, 11
Bottom-Up Merge Sort
Informally, the algorithm does the following
1. Divide the array into pairs of elements (with possibly a single elements in case the number of elements is odd). 2. Merge each pair in non-decreasing order (with possibly a single pair left) 3. Repeat step 2 until there is only one pair left.
20
Thursday, September 15, 11
Bottom-Up Merge Sort Example
2 9 8
4 12 7
3 6 10
21
Thursday, September 15, 11
Bottom-Up Merge Sort Example
5 5
2 2 9 8 4 12 7 1 3 6 10
21
Thursday, September 15, 11
Bottom-Up Merge Sort Example
5 5
8 4 12 7 1 3 6 10
21
2 9 8
Thursday, September 15, 11
Bottom-Up Merge Sort Example
5 5
4 12 4 12 7 1 3 6 10
21
2 9 8
Thursday, September 15, 11
Bottom-Up Merge Sort Example
5 5
4 12 4 12 7
7 1
1 3 6 10
21
2 9 8
Thursday, September 15, 11
Bottom-Up Merge Sort Example
5 5
4 12 4 12 7
7 1
2 9 8
3 6 10
21
Thursday, September 15, 11
Bottom-Up Merge Sort Example
5 5
4 12 4 12 7
7 1
10
2 9 8
3 6 10
21
Thursday, September 15, 11
Bottom-Up Merge Sort Example
2 5 5 5 2
8 9
9 8
4 12 4 12 4 12 7
1 7 7 1 1
3 6 3 6
10 10
2 9 8
3 6 10
21
Thursday, September 15, 11
Bottom-Up Merge Sort Example
2 5 2 5 5 5 2
8 8 9
9 9 8 4 12 4 12 4 12 7 1 7 7 1 1 3 6 3 6 10 10
2 9 8
3 6 10
21
Thursday, September 15, 11
Bottom-Up Merge Sort Example
2 5 2 5 5 5 2
8 8 9
9 9 8
4 7 12 1 7 7 1 1 3 6 3 6 10 10
4 12 4 12 4 12 7
2 9 8
3 6 10
21
Thursday, September 15, 11
Bottom-Up Merge Sort Example
2 5 2 5 5 5 2
8 8 9
9 9 8
4 7 12 1 7 7 1 1
3 6 10 3 6 3 6 10 10
4 12 4 12 4 12 7
2 9 8
3 6 10
21
Thursday, September 15, 11
Bottom-Up Merge Sort Example
1 2 5 2 5 5 5 2 2 4 8 8 9 5 7 9 9 8 1 8 9 12 4 7 12 1 7 7 1 1 3 6 10 3 6 3 6 10 10
4 12 4 12 4 12 7
2 9 8
3 6 10
21
Thursday, September 15, 11
Bottom-Up Merge Sort Example
1 2 5 2 5 5 5 2 2 4 8 8 9 5 7 9 9 8 1 8 9 12 4 7 12 1 7 7 1 1 3 6 10 3 6 10 3 6 3 6 10 10
4 12 4 12 4 12 7
2 9 8
3 6 10
21
Thursday, September 15, 11
Bottom-Up Merge Sort Example
1 1 2 5 2 5 5 5 2 2 3 4 2 4 8 8 9 5 6 7 8 1 9 8 8 9 10 12 3 6 10 3 6 10 3 6 3 6 10 10 5 7 9 9 12 4 7 12 1 7 7 1 1
4 12 4 12 4 12 7
2 9 8
3 6 10
21
Thursday, September 15, 11
Algorithm BOTTOMUPSORT
Algorithm: BOTTOMUPSORT Input: An array A[1..n] of n elements. Output: A[1..n] sorted in nondecreasing order. 1. t 1 2. while t < n 3. s t; t 2s; i 0 4. while i + t n 5. MERGE(A, i + 1, i + s, i + t) 6. i i + t 7. end while 8. if i + s < n then 9. MERGE(A, i + 1, i+ s, n) 10. end while
22
Thursday, September 15, 11
Analyzing Algorithm
With no loss of generality, assume the size of the array is a power of 2.
n In the first iteration, we have pairs that are merged using 2 n * 2 * 2 = 2n element assignments. 2
In the first iteration, we have
n * 4 * 2 = 2n assignments. 4
.
n 4
pairs that are merged using
In the last iteration, we have 1 pair that are merged using element
n 2 * 2 * = 2n 2
Thursday, September 15, 11
assignments.
23
Analyzing Algorithm BOTTOMUPSORT
Number of iterations is log n, since the number of pairs is reduced by half in each iteration. Hence, run time is 2n x log n = O(n log n).
24
Thursday, September 15, 11
Time Complexity
One way of measuring the performance of an algorithm is how fast it executes. The question is how to measure this time?
Is having a digital stop watch suitable?
In general, we are not so much interested in the time and space complexity for small inputs. For example, while the difference in time complexity between linear and binary search is meaningless for a sequence with n = 10, it is gigantic for n = 230.
25
Thursday, September 15, 11
Complexity
For example, let us assume two algorithms A and B that solve the same class of problems. The time complexity of A is 5,000n, the one for B is 1.1n for an input with n elements. For n = 10, A requires 50,000 steps, but B only 3, so B seems to be superior to A. For n = 1000, however, A requires 5,000,000 steps, while B requires 2.51041 steps.
26
Thursday, September 15, 11
Complexity
Comparison: time complexities of algorithms A and B
Input Size n 10 100 1,000 1,000,000
Algorithm A 5,000n 50,000 500,000 5,000,000 5109
Algorithm B 1.1n 3 13,781 2.51041 4.81041392
28
Thursday, September 15, 11
Order of Growth
This means that algorithm B cannot be used for large inputs, while algorithm A is still feasible. So what is important is the growth of the complexity functions. The growth of time and space complexity with increasing input size n is a suitable measure for the comparison of algorithms. we focus on asymptotic analysis
28
Thursday, September 15, 11
Example
Growth rate for some function
Thursday, September 15, 11
29
Example
Growth rate for same previous functions showing larger input sizes
30
Thursday, September 15, 11
Running Times for Different Sizes of Inputs of Different Functions
31
Thursday, September 15, 11
Running Times for Different Sizes of Inputs of Different Functions
Complexity
n n2 n3 n5 2n 3n log2 n
10 110-5 sec 0.0001 sec 0.001 sec 0.1 sec 0.001sec 0.59sec
20 210-5 sec 0.0004 sec 0.008 sec 3.2 sec 1.0 sec 58 min
30 310-5 sec 0.0009 sec 0.027 sec 24.3 sec 17.9 min 6.5 years
40 410-5 sec 0.016 sec 0.064 sec 1.7 min 12.7 days 3855 cent
50 510-5 sec 0.025 sec 0.125 sec 5.2 min 35.7 years 2108cent
60 610-5 sec 0.036 sec 0.216 sec 13.0 min 366 cent 1.31013cent
310-6 sec 410-6 sec 510-6 sec 510-6 sec 610-6 sec 610-6 sec
n log2 n 310-5 sec 910-5 sec 0.0001 sec 0.0002 sec 0.0003 sec 0.0004 sec
31
Thursday, September 15, 11
Asymptotic Analysis: Big-oh (O())
Definition: For T(n) a non-negatively valued function, T(n) is in the set O(f(n)) if there exist two positive constants c and n0 such that T(n) cf(n) for all n > n0. Meaning: For all data sets big enough (i.e., n>n0), the algorithm always executes in less than or equal to cf(n) steps.
32
Thursday, September 15, 11
The Growth of Functions
The idea behind the big-O notation is to establish an upper boundary for the growth of a function f(n) for large n. This boundary is specified by a function g(n) that is usually much simpler than f(n). We accept the constant c in the requirement f(n) cg(n) whenever n > k, because c does not grow with n. We are only interested in large n, so it is OK if f(n) > cg(n) for n k.
33
Thursday, September 15, 11
The Growth of Functions
Enample: Show that f(n) = n2 + 2n + 1 is O(n2). For n > 1 we have: n2 + 2n + 1 n2 + 2n2 + n2 n2 + 2n + 1 4n2 Therefore, for c = 4 and k = 1: f(n) cn2 whenever n > k. f(n) is O(n2).
34
Thursday, September 15, 11
The Growth of Functions
Question: If f(n) is O(n2), is it also O(n3)? Yes. n3 grows faster than n2, so n3 grows also faster than f(n). Therefore, we always try to find the smallest simple function g(n) for which f(n) is O(g(n)).
35
Thursday, September 15, 11
The Growth of Functions
Popular functions g(n) are n log n, 1, 2n, n2, n!, n, n3, log n Listed from fastest to slowest growth: 1 log n n n log n n2 n3 2n n!
36
Thursday, September 15, 11
Asymptotic Analysis: Big-Omega (())
Definition: For T(n) a non-negatively valued function, T(n) is in the set (g(n)) if there exist two positive constants c and n0 such that T(n) >= cg(n) for all n > n0. Meaning: For all data sets big enough (i.e., n > n0), the algorithm always executes in more than or equal to cg(n) steps. () notation indicates a lower bound.
37
Thursday, September 15, 11
Asymptotic Analysis: Big Theta (())
When O() and () meet, we indicate this by using () (big-Theta) notation. Definition: An algorithm is said to be (f(n)) if it is in O(f(n)) and it is in (f(n)).
38
Thursday, September 15, 11
Using the limit criterion
Let
f (n) L = lim n g(n)
- If L , then - If L 0, then - If L = c > 0 , then
Thursday, September 15, 11
f (n) = O(g(n))
f (n) = (g(n)) f (n) = (g(n))
41
Summary
f (n) = O(g(n)) if
f (n) lim n g(n)
f (n) = (g(n)) if g(n) = O( f (n))
f (n) = O(g(n)) and f (n) = (g(n)) if f (n) = (g(n)) f (n) = O(g(n)) and f (n) = (g(n)) if g(n) = O( f (n))
42
Thursday, September 15, 11
Examples 1
Hence,
It follows that
44
Thursday, September 15, 11
Examples 2
Hence,
It follows that
45
Thursday, September 15, 11
Examples 3
Since 100 > 0, This implies that and
46
Thursday, September 15, 11
Example 4
Prove that We only need to show that the two functions are not related by O or
Hence, Or
which means
Since the limit is not a constant > 0,
47
Thursday, September 15, 11
Example 5
Show that log(n!) is in (n log n).
39
Thursday, September 15, 11
Estimating the Running Time of an Algorithm
We need to focus on counting those operations which represent, in general, the behavior of the algorithm This is achieved byCounting the frequency of basic operations. A Basic operation is an operation with highest frequency to within a constant factor among all other elementary operations
50
Thursday, September 15, 11
Computing running time continued..
54
Thursday, September 15, 11
Number of iterations (additions)
16
Thursday, September 15, 11
Number of iterations (additions)
While Iteration 1 2 3 .. k # of additions n n/2 n/4 .. n/n
16
Thursday, September 15, 11
Number of iterations (additions)
While Iteration 1 2 3 .. k # of additions n n/2 n/4 .. n/n
16
Thursday, September 15, 11
54
Thursday, September 15, 11
Example 1.23
Consider Algorithm count2, which con loops and a variable count which counts the number of itera Computing running time positive integer. the algorithm on input n, which is acontinued.. Algorithm 1.9 count2 Input: A positive integer n. Output: count = number of times Step 5 is executed. 1. 2. 3. 4. 5. 6. 7. 8. count 0 for i 1 to n m n/i for j 1 to m count count + 1 end for end for return count
51
Thursday, September 15, 11
The inner for loop is executed repeatedly for the followin
Number of iterations (additions)
16
Thursday, September 15, 11
Number of iterations (additions)
While Iteration 1 2 3 .. n # of additions n n/2 n/3 .. n/n
16
Thursday, September 15, 11
Number of iterations (additions)
While Iteration 1 2 3 .. n
n i=0
# of additions n n/2 n/3 .. n/n
n i
n i=0
n 1 =n = O(n log n). i i i=0
16
Thursday, September 15, 11
the algorithm on input n, which is a positive integer. Algorithm 1.9 count2 Input: A positive integer n. Output: count = number of times Step 5 is executed. 1. 2. 3. 4. 5. 6. 7. 8. count 0 for i 1 to n m n/i for j 1 to m count count + 1 end for end for return count n n
n 1 =n = O(n log n). i i Theiinner for loop is executed repeatedly for the followin i=0 i=0 i=0
53
Thursday, September 15, 11
n, n/2 , n/3 , . . . , n/n .
Useful Summation Formulas
54
Thursday, September 15, 11
Useful Summation Formulas
Pn
j=1 j = n(n+1) 2
= (n2 )
54
Thursday, September 15, 11
Useful Summation Formulas
Pn Pn
j=1 j = j=0 j n(n+1) 2
= (n2 ) 6= 1
a =
an+1 1 a 1 ;a
54
Thursday, September 15, 11
Useful Summation Formulas
Pn Pn
Pn
j=1 j = j=0 j n(n+1) 2
= (n2 ) 6= 1
a =
an+1 1 a 1 ;a
1 n
1 j=0 2j
=2
= (1)
54
Thursday, September 15, 11
Useful Summation Formulas
Pn Pn
Pn
j=1 j = j=0 j n(n+1) 2
= (n2 ) 6= 1
a =
an+1 1 a 1 ;a
1 n
1 j=0 2j
=2
= (1)
Pn
Thursday, September 15, 11
1 j=1 j
ln n = (log n)
54
Space Complexity
Space complexity refers to the number of memory cells needed to carry out the computational steps required in an algorithm excluding memory cells needed to hold the input. Compare additional space needed to carry out SELECTIONSORT to that of BOTTOMUPSORT if we have an array with 2 million elements!
48
Thursday, September 15, 11
Examples
What is the space complexity for
Linear search Binary search Selection sort Insertion sort Merge (that merges two sorted lists) Bottom up merge sort
49
Thursday, September 15, 11
Complexity Classes and small-oh (o())
Using () notation, one can divide the functions into different equivalence classes, where f(n) and g(n) belong to the same equivalence class if f(n) = (g(n)) To show that two functions belong to different equivalence classes, the small-oh notation has been introduced Definition: Let f(n) and g(n) be two functions from the set of natural numbers to the set of non-negative real numbers. f(n) is said to be in o(g(n)) if for every constant c > 0, there is a positive integer n0 such that f(n) < cg(n) for all n n 0.
40
Thursday, September 15, 11
