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 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.
The Java API provides method isProbablePrime(int certainty) in class java.math.BigInteger. The idea is that certainty tells how certain you want the result to be. When x.isProbablePrime(c) returns true, the probability that x the result is incorrect is less than 2−c. If you want to use it on a value of type long, you need to convert to a BigInteger. Here is a definition of isPrime using that idea, assuming that java.math.BigInteger has been imported.
static boolean isPrime(long n)
{
BigInteger b = BigInteger.valueOf(n);
return b.isProbablePrime(20);
}
Using Θ notation, say how much time the following method uses, as a function of the length n of string s. (Computing s.length() for a string s takes O(1) time.)
String vowels = "aeiouAEIOU";
static int numVowels(String s)
{
int count= 0;
for(int i = 0; i < s.length(); i++)
{
if(vowels.indexOf(s.charAt(i)) >= 0)
{
count++;
}
}
return count;
}
Answer