Analyze an algorithm and determine its run-time complexity using Big-O notation.

Question

Analyze an algorithm and determine its run-time complexity using Big-O notation. Match the letters to each numbered statement.

A. O(1) Constant time

B. O(log n) Logarithmic time

C. O(n) Linear time

D. O(n2) Quadratic

E. O(2n) Exponential

1. Multiply two numbers by long-hand

2. Find the name of a person with a given phone number in a phone book

3. Crack a binary passcode of n digits by brute force

4. Compute the area of a circle given the circumference

5. Find an item in a sorted array

6. Determine if a binary number is even or odd

7. Find the definition of a given word in a dictionary

8. Find an item in an unsorted array

9. Determine if two logical statements are equivalent by brute force

10. Find the phone number in a phone book, given a person’s name

11. Find the word that fits a given definition in a dictionary

12. Retrieve the nth element from an array

13. Given a set of keys and a set of locks find which keys open which locks

14. Selection sort

15. Find the shortest route to visit n cities by air plane

Explanation / Answer

1. Multiply two numbers by long-hand
since directly we can Multiply in one step so it will be O(1)

---------------------------------------------------------------------------
2. Find the name of a person with a given phone number in a phone book
if we search for name which is in last page.....then we have asearch all names till it found..so if N names are there..
then in worst case..it will take O(N)

------------------------------------------------------------------------------
3. Crack a binary passcode of n digits by brute force
Brute force method it will do searching and sorting parallely..so it will take O(n2)

-------------------------------------------------------------------------------------
4. Compute the area of a circle given the circumference
calculating area can be done in single step ...so O(1)

--------------------------------------------------------------------------------------
5.Find an item in a sorted array
if we search for name which is in last of the array.....then we have to search all names till it found..so if N items are there..
then in worst case..it will take O(N)
-----------------------------------------------------------------------------------------
6. Determine if a binary number is even or odd
If last sognificant or last bit in the sequence is 0 thrn it is even otherwise it is odd...so ne step O(1)
-------------------------------------------------------------------------------------------
7.Find the definition of a given word in a dictionary
since it is pattern match..it have to check all records so O(n)
-----------------------------------------------------------------------------------------------
8. Find an item in an unsorted array
we have to search every element in array till we get the value...so O(n)
---------------------------------------------------------------------------------------------------------
9. Determine if two logical statements are equivalent by brute force
since it have to search dynamically parallelytwo logical statements...so it will take exponemtial..O(2n)
-------------------------------------------------------------------------------------------------

10. Find the phone number in a phone book, given a person’s name
since persons name may contain more than one...so we have to search entire all records...so it will take O(n)
------------------------------------------------------------------------------------------

11.Find the word that fits a given definition in a dictionary
it have to search actual word and also reverse search to find for best fot..so exponential O(2n)

-------------------------------------------------------------------------------

12. Retrieve the nth element from an array
it is single step...for example if we want 5th element ...then array[5] will give fifith element..so O(1)
--------------------------------------------------------------------------------

13. Given a set of keys and a set of locks find which keys open which locks
we have to search key and locks parallely...so two operations..so O(n2)

----------------------------------------------------------------------------------
  
14. Selection sort
it has to max value and place it right place..so O(n2)

---------------------------------------------------------------------------
  
15. Find the shortest route to visit n cities by air plane
it have to permuatate n-1 cities.....so O(n!)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.