Preview

01 - Comparison of Algorithms

 1. In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively

  FALSE

  TRUE

 2. In real-time computing, the best-case execution time is often of particular concern since it is important to know how much time might be needed in the best case to guarantee that the algorithm will always finish on time.

  FALSE

  TRUE

 3. Computer A appears to be running an algorithm that is more efficient. What do we need to do to truly test the algorithms? 
Take as an example a program that looks up a specific entry in 
a sorted list of size n. 

Suppose this program were implemented on Computer A, a 
state-of-the-art machine, using a linear search algorithm, 
and on Computer B, a much slower machine, using a binary 
search algorithm. Benchmark testing on the two computers 
running their respective programs might look something 
like the following: (see image)

Based on these metrics, it would be easy to jump to the 
conclusion that Computer A is running an algorithm that 
is far superior in efficiency to that of Computer B.

What needs to be considered (and added to the tests)
to truly test the efficiency of the algorithm?

*Source: https://en.wikipedia.org/wiki/Analysis_of_algorithms
comparison_of_AandB.png

  The size of the input-list could be increased greatly

  The size of the input-list could be decreased greatly

  The run time of both computers could be decreased

  The run time of both computers could be increased

 4. Computer A, running the linear search program, exhibits a linear growth rate. The program's run-time is _________________________ 
On the other hand, Computer B, running the binary search program, exhibits a logarithmic growth rate. Quadrupling the input size only increases the run time by a constant amount

  directly proportional to its input size

  always half its input size

  indirectly related to its input size

  always triple its input size

 5. The followning algorithms/groups of statements are examples that have a time complexity of: 
1. Accessing Array Index (int a = ARR[5];)
2. Inserting a node in Linked List
3. Pushing and Poping on Stack
4. Insertion and Removal from Queue
5. Finding out the parent or left/right child of a node in a tree stored in Array
6. Jumping to Next/Previous element in Doubly Linked List
and you can find a million more such examples...

  O(1) time

  O(n) time

  O(nlogn) time

  O(log n) time

 6. The best case time complexity for the merge sort is:

  O(n)

  O(n^2)

  O(n log(n))

  O(1)

 7. The best case time complexity for the insertion sort is:

  O(1)

  O(n log(n))

  O(n^2)

  O(n)

 8. Th worst case time complexity for the insertion sort is:

  O(1)

  O(n)

  O(n^2)

  O(n log(n))

 9. Th worst case time complexity for the bubble sort is:

  O(n^2)

  O(n log(n))

  O(1)

  O(n)

 10. If your priority was to ensure the quickest possible 'access by index', you would be most likely to use:

  an array O(1)

  a stack and a queue combined O(n^2)

  None of these options are valid

  a linked list O(n)

 11. The addition feature in an array would be O(n) and in a linked list would be:

  O(n)

  O(n^2)

  O(1)

  O(n log(n))

 12. The worst case space complexity for Merge sort is:

  O(n*m)

  O(n)

  O(n^2)

  O(1)

 13. The worst case space complexity for Bubble sort is:

  O(1)

  O(n*m)

  O(n)

  O(n^2)

 14. O(n) access time would mean whether you're accessing from 100 or 100,000 records, the retrieval time will be the same

  TRUE

  FALSE

 15. A simple example of O(1) might be return 23; -- whatever the input, this will return in a fixed, finite time

  O(n*m)

  O(1)

  O(n^2)

  O(n)

 16. A typical example of O(n) would be sorting an input array with a good algorithm (e.g. mergesort).

  FALSE

  TRUE


Report an error