a. Give the formal definition of big-O and big-theta
b. Prove or disprove that for any three functions f(x), g(x) and s(x): s(x)=O(f(x)) and s(x)=O(g(x)) imply s(x) = O((max(f(x), g(x))), but does not imply max(f(x), g(x)) = O(s(x))
* Suppose: and
(1)
(2)
(1) and (2) imply that we can introduce the two real numbers C1 and C2 and the two integers n1 and n2 such that:
(3)
(4)
Let:
and
Then from (3) and (4), we have:
(5)
(6)
Let k be a natural integer, we have two different cases:
1)
In this case:
(7)
So, (5) implies that:
2)
In this case:
(8)
So, (6) implies that:
(9)
In both cases (9) holds. As this was shown for any k, we can write:
Which implies that:
Which basically means:
This is what we wanted to prove.
Now suppose again: and
Consider these specific functions s, f and g:
Note that:
These functions respect the hypothesis, but the following relation does not hold:
Therefore s(x)=O(f(x)) and s(x)=O(g(x)) does not imply max(f(x), g(x)) = O(s(x)).
c. Consider and
prove or disprove these two statements:
h(x)=O(k(x)) and k(x)=O(h(x))
Let’s prove that h(x)=O(k(x))
We know:
(1)
(2)
(3)
We have:
(4)
On the other hand, we have:
(5)
Because the two functions and
take only positive values when x is positive, (5) implies
that:
(6)
Now:
Let’s prove that k(x)=O(h(x)) is not implied:
Suppose k(x) = O(h(x)):
Then:
Let C1 and n1 be such constants:
(1)
But it is easy to show that:
(2)
(1) and (2)are incompatible, so our supposition was wrong. The statement k(x) = O(h(x)) is false.
Note: the formal reason why (1) and (2) are not compatible is the definition of the limit:
Implement the function
int match(int a[], int b[], int N, int M);
// The following code does a binary search on A[] for // Each element in B int match(int A[], int B[],int N, int M) { int j; int count=0; for(j=0;j<M;j++) count+=bsearch(A,N,B[j]); return count; } int bsearch(int A[],int N,int what) { int r=N, l=0; int c; while (r >= l) { c=(l+r)/2; if (what == A[c]) return 1; if (what < A[c]) r = c-1; else l = c+1; } return 0; }
Complexity is O(N1/2*lg(N)).
The reason is that we perform M binary searches. Each binary search
takes O(lg(N)) time. And M is equal to the square root of N.
I'd use a different algorithm. Specifically I'd take the intersection of A
and B as was done in the homework. This is O(N). The algorithm from part a
would actually run in O(N*lg(N)) time if M=N.
Write a function which takes two sorted, NULL-terminated, linked lists as arguments. You are to return a pointer to a sorted, NULL-terminated, linked list which is a merge of the two lists. You must not change either of the two linked lists passed in.
#include <string.h> // for strcmp // Client structure, with addition of "next" pointer struct Client { char f_name [40]; // first name char l_name [40]; // last name double money; // how much money do they have? Client * next; // pointer to next node }; /* operator< Returns true if client a is less than client b in lexicographic order. */ bool operator< (const Client & a, const Client & b) { if (strcmp (a.l_name, b.l_name) < 0) return true; if (strcmp (a.l_name, b.l_name) == 0) // if last names are the same if (strcmp (a.f_name, b.f_name) < 0) return true; return false; } // operator< /* addToList A utility function to aid in constructing result list. Takes a pointer to an item to add and pointers to the head and tail of the result list, and adds the new item to the tail of the result list. */ void addToList (Client * newItemIter, Client * & resultHead, Client * & resultTail) { Client * newNode = new (Client); *newNode = *newItemIter; // default assignment operator does most of the work newNode -> next = NULL; if (resultHead == NULL) // if result list was empty { resultHead = newNode; resultTail = newNode; } else { resultTail -> next = newNode; resultTail = newNode; } } // addToList /* merge The main function. */ Client * merge (Client * oldlist, Client * newlist) { Client * olditer = oldlist; // iterator for stepping through old list Client * newiter = newlist; // iterator for stepping through new list Client * resultHead = NULL; // the list we'll return Client * resultTail = NULL; while (olditer || newiter) // while at least one list not at end { if (!olditer) // if only new list remains... { addToList (olditer, resultHead, resultTail); olditer = olditer -> next; // step through old list } else if (!newiter) // if only old list remains... { addToList (newiter, resultHead, resultTail); newiter = newiter -> next; // step through new list } else if ((*olditer) < (*newiter)) // if old list is behind new one... { addToList (olditer, resultHead, resultTail); olditer = olditer -> next; // step through old list } else if ((*newiter) < (*olditer)) // if new list is behind old one... { addToList (newiter, resultHead, resultTail); newiter = newiter -> next; // step through new list } else // iterators point to equal items { addToList (newiter, resultHead, resultTail); // we want the new money value olditer = olditer -> next; // step through old list newiter = newiter -> next; // step through new list } } return (resultHead); } // merge
4,0,9,2,3,6,7,1,8,5 4,9,2,3,6,7,1,8,5,0 9,4,3,6,7,2,8,5,1,0 9,4,6,7,3,8,5,2,1,0 9,6,7,4,8,5,3,2,1,0 9,7,6,8,5,4,3,2,1,0 9,7,8,6,5,4,3,2,1,0 9,8,7,6,5,4,3,2,1,0
Can't be merge sort, takes too long. Can't be selection or insertion as 9 and 4 swap places in line 3. Can't be shaker as 8 isn't in place until the end. Is bubble sort. Next smallest is always in place at end of the pass. Large values always move exactly 1 spot to their left each pass.
selection(Item a[], int l, int r) { for (int i = l; i < r; i++) { int min = i; for (int j = i+1; j <= r; j++) if (a[j] < a[min]) min = j; exch(a[i], a[min]); } }Both best and worse case are big-Theta(N2). The outer for loop runs through every itelm in the array. The inner for loop runs though half of the items in the array on average. This is big-Theta(N2).
The best and worse case are more-or-less the same, both do exactly the same number of comparisions. However a sorted list will do no actual swaps and the condidtion of the if statement will ever be executed, a slight savings. By the same arguement having a reverse-sorted list would provide the maximum number of swaps possible.