Ok so I have to make a time analysis table for both of my binary search algorithms in my program. One is recursive and the other isn't. This is for a spellchecker program that has a dictionary file that has all the correctly spelled words and an input file that we check for correctness. The d[] array in the search functions is the dictionary that I have put into an array and the "find" variable is a word from the input.
I have a loop in my main that sends each word from the input array to one these functions. (They aren't run at the same time. I will be using one or the other)
Here is my non-recursive one:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
int bSearch(string d[], int size, string find)
{
int first = 0;
int last = size - 1;
int mid;
int pos = -1;
Count += 4;
bool found = false;
Count++;
while (!found && first <= last)
{
Count++;
mid = (first + last) / 2;
Count++;
if (d[mid] == find)
{
Count++;
found = true;
pos = mid;
Count += 2;
}
else if (d[mid] > find)
{
Count++;
last = mid - 1;
}
else
{
Count++;
first = mid + 1;
}
}
return pos;
}
|
Here is my recursive version:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
|
int rbSearch(string d[], int begin, int end, string find)
{
Count++;
if(begin > end)
{
Count++;
return -1;
}
int middle;
middle = begin + (end - begin)/2;
Count++;
if(d[middle] == find)
{
Count++;
return middle;
}
else if(d[middle] < find)
{
Count++;
return rbSearch(d, middle+1, end, find);
}
else
{
Count++;
return rbSearch(d, begin, middle-1, find);
}
}
|
Count is my attempt at counting the number of operations. My instructions say to only count one operation per line (including comparisons, assignments, and function calls).
(so if I have a for loop like for(int i = 0; i < n-1; i++) that only counts as one in that operation, not three)
I then need to calculate the T(n) for both of these which I have absolutely no clue how to do. I know that binary search is O(logn) and I know that deriving T(n) has something to do with counting the operations, but I have no idea how to apply that, especially with log involved.
Here is an example I was given of what the table should look like:
1 2 3 4 5 6 7 8 9 10 11
|
BINARY SEARCH
c=9.999
n_0=100
n #operations T(n) O(f(n))
========================================-
100 99 99 999
1000 99 99 999
10000
100000
|
I know that n is supposed to be input, but I don't know if it should be the number of items in the dictionary, the number of items in the input, or both.
I also can't figure out what c and n_0 are supposed to be. All I've got for n_0 so far is "n_0 is the smallest value of n for which the inequality holds true". And as far as I can tell, c is some sort of constant.
I'm also unsure what O(f(n)) is, but from what I've been told it is basically you plugging n into your Big-O equation. So if binary search is O(logn) and I have n = 100, then O(f(n)) is something like log(100).
I'm sure a lot of this sounds wrong, but it's a start, hopefully....
I was also told that my T(n) does not have to be perfect or precise it just needs to be a kinda close/sloppy estimate.
Oh and it sounds like the 100 on that table is the actual input size and the 1000, 10000, 100000 are "synthetic" data that the program is supposed to be able to calcuate the T(n)'s value (after plugging n into it, I assume) using the equation I came up with. So I guess I will multiply it by something?
Thanks in advance!