# Find out which of the following are true:

- A Θ( n ) algorithm is O( n )
- A Θ( n ) algorithm is O( n
^{2} )
- A Θ( n
^{2} ) algorithm is O( n^{3} )
- A Θ( n ) algorithm is O( 1 )
- A O( 1 ) algorithm is Θ( 1 )
- A O( n ) algorithm is Θ( 1 )

###
Solution

- We know that this is true as our original program was Θ( n ). We can achieve O( n ) without altering our program at all.
- As n
^{2} is worse than n, this is true.
- As n
^{3} is worse than n^{2}, this is true.
- 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).
- This is true as the two complexities are the same.
- 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 ).

## 0 comments:

Feel free to contact the admin for any suggestions and help.