# 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

TRUE

FALSE

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``` The size of the input-list could be increased greatly

The run time of both computers could be decreased

The run time of both computers could be increased

The size of the input-list could be decreased greatly

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

indirectly related to its input size

always half 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;)
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(n) time

O(log n) time

O(1) time

O(nlogn) time

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

O(1)

O(n)

O(n^2)

O(n log(n))

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

O(n)

O(1)

O(n^2)

O(n log(n))

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

O(1)

O(n^2)

O(n)

O(n log(n))

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

O(n)

O(1)

O(n log(n))

O(n^2)

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

None of these options are valid

an array O(1)

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

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)

O(1)

O(n*m)

O(n^2)

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

O(n*m)

O(n)

O(n^2)

O(1)

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(1)

O(n)

O(n*m)

O(n^2)

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

TRUE

FALSE