Find out which of the following are true:

1. A Θ( n ) algorithm is O( n )
2. A Θ( n ) algorithm is O( n² )
3. A Θ( n² ) algorithm is O( n³ )
4. A Θ( n ) algorithm is O( 1 )
5. A O( 1 ) algorithm is Θ( 1 )
6. A O( n ) algorithm is Θ( 1 )

Solution

1. We know that this is true as our original program was Θ( n ). We can achieve O( n ) without altering our program at all.
2. As n² is worse than n, this is true.
3. As n³ is worse than n², this is true.
4. As 1 is not worse than n, this is false. If a program takes n instructions asymptotically (a linear number of instructions), we can't make it worse and have it take only 1 instruction asymptotically (a constant number of instructions).
5. This is true as the two complexities are the same.
6. This may or may not be true depending on the algorithm. In the general case it's false. If an algorithm is Θ( 1 ), then it certainly is O( n ). But if it's O( n ) then it may not be Θ( 1 ). For example, a Θ( n ) algorithm is O( n ) but not Θ( 1 ).