We will look at the time used by some simple algorithms. In all cases, we look at the worst case time, that is, the maximum time taken for any input of length n.
To add up all of the members of an array that has n members takes time Θ(n). You do one addition per number.
To compute the length of a linked list takes time Θ(n). You need to look at each cell once as you traverse the list.
To look up a value in a balanced binary search tree that has n things in it takes time Θ(log_2(n)).
To sort an array of n integers using Heapsort takes time Θ(nlog2(n)).
To sort an array of n integers using Insertion Sort takes time Θ(n2).
You can test whether an integer x is prime by trying each integer k from 2 to the square root of x to see if k is a factor of x. Remember that we express the cost of an algorithm in terms of the number of characters it takes to write it down. For an integer, that is the number of digits needed.
Assuming no leading zeroes, an n digit number is between 10n−1 and 10n. Since we are looking at the worst case, let's say that n-digit number x is roughly 10n. So the square root of x is roughly 10n/2. If x is prime, we will need to try that many values of k. So the time is surely at least 10n/2. That is the time is Ω(10n/2).
If n = 100 then we need to try about 1050 values of k. That is, very roughly, the number of protons in the earth.
Just because one algorithm for a given problem is slow does not mean that all possible algorithms for that problem are slow. For example, Heapsort and Insertion Sort both sort an array, but Heapsort is much faster.
There are much faster algorithms for determining whether a number is prime than the obvious algorithm. In fact, it is quite practical to test whether a 1000 digit number is prime. The nature of the faster algorithms to test primality is beyond this course, but you should not be surprised when an algorithm that is much faster than an obvious algorithm is discovered.
Using Θ notation, say how much time the following function uses, as a function of the length n of string s.
char* vowels = "aeiouAEIOU";
int numVowels(char* s)
{
int count= 0;
for(int i = 0; s[i] != '\0'; i++)
{
if(strchr(vowels, s[i]) != NULL)
{
count++;
}
}
return count;
}
Answer
Same as the preceding question, but for the following function.
char* vowels = "aeiouAEIOU";
int numVowels(char* s)
{
int count= 0;
for(int i = 0; i < strlen(s); i++)
{
if(strchr(vowels, s[i]) != NULL)
{
count++;
}
}
return count;
}
Answer