How to do time complexity table for binary search? (recursive and non-recursive)

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!
Last edited on
Important are the lines 15 and 12, respectively. These are the lines that bound your loops (explicit or recursive).

Those two lines HALVE the number of times remaining through the loop/recursion, which is a log(n) complexity.

Everything else has no effect on the loop whatsoever → O(1).

(However, you may be asked to compare which algorithm is more expensive in terms of operations performed per iteration/recursive call.)


Consider binary numbers. If counting by one, you get to 1 instantly. It takes twice as long to count to 2. Four times as long to count to 4. Eight times as long to count to eight...

Written another way, it is 20, 21, 22, 23, ..., 2log2(n).

Why log2(n)? Because of the relation between exponents and logarithms.

Hope this helps.
It sounds like useful innfo, but I'm not sure how to use it to derive T(n).

This is what I have for my T(n)'s so far:

recursive: InputSize * (3log2(n)+3)
non-recursive: InputSize * (3log2(n)+6)

Both of these equations give me a T(n) that is just a little above the actual number of operations. My problem is that I feel like I got these mainly through guess work, so I have no clue if they are actually correct.

Do these look good enough? If not, what do I need to do?
big-o does not generally use constants.

no one cares if its log or lg or ln. Its just called log. No one cares if it takes N+11 operations, it is just cut to N. Constant multipliers are iffy... usually those are also N.
So the above in big O is just Nlog(N), and both functions are equally complex.

Counting high level statements is frustrating, one statement might be 100 cpu instructions and another only 5.

The truth is in the run-time anyway. If serious about it, I would get the cpu clock count for each and compare them. Whichever one is higher is taking longer. You can also use various timers to count the wall clock time consumed. Then you can try to find tweaks to lower these values for the better algorithm. You may even discover that a dumb O(N) check every value is faster than all the extra work done to save time for small* lists...

many like to look at best/worst/average case times. For a b-search, that is 1(lucky, found it first thing) vs average (nlog(n)/2) vs worst (nlog(n) but average has that pesky constant 1/2.

*small varies by hardware.
Last edited on
Topic archived. No new replies allowed.