Question

1. State and explain the definition of big-O.
2. Explain why we use big-O to compare algorithms.
3. Explain why binary search runs in O(log n) time.
4. Under what conditions is it possible to sort a list in less than O(nlog n) time?
5. List and explain the worst-case and average-case running times for each Vector method below:
(a) insert(iterator here, Object item)

(b) insertAtHead

(c) insertAtTail (aka push back)

(d) get(iterator here)

(e) get(index i)

(f) remove(iterator here)

(g) remove(index i)

(h) splice(iterator place here, iterator from here, iterator to here)
(Be sure you understand when (and why) push back runs in constant average time.)

6. List and explain the worst-case and average-case running times for each LinkedList method below:
(a) insert(iterator here, Object item)

(b) insertAtHead

(c) insertAtTail (aka push back)

(d) get(iterator here)

(e) get(index i)

(f) remove(iterator here)

(g) remove(index i)

(h) splice(iterator place here, iterator from here, iterator to here)
7. When should you use a Vector, and when should you use a Linked List?

8. Assume you have a singly linked list with no tail pointer. Implement removeTail(). Raise an exception of the method is called on an empty list.
template<typename Object> class LinkedList {
private:

class Node {

Object data;

Node* next;

};

Node *head;
public:

LinkedList() : head(nullptr) {}

Object removeTail(Object data);

};

9. What are iterators? What purpose do they serve?
10. What does it mean to invalidate an iterator?
11. Explain the difference between separate chaining and open addressing in hash tables.
12. Define load factor and explain its relevance to hash table performance.
13. What are collisions with respect to hash tables?
14. Which hash tables distinguish between slots that have never been used, and slots that once contained an item but has now been deleted.
15. List and explain the worst-case and average-case running times for each HashTable method below
(a) void insert(Key k, Value v)

(b) bool contains(Key k)

(c) Value get(Key k)

Answer 1

1.Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".

Formal Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.
Big O notation is a convenient way to describe how fast a function is growing.With Big O Notation we express the runtime in terms of — how quickly it grows relative to the input, as the input gets larger.

cg (n) f(n)

2.

Big O Notation helps to identify

1. how quickly the runtime grows — Being that it is difficult to determine the exact runtime of an algorithm. It depends on the speed of the computer processor. So instead of talking about the runtime directly, we use Big O Notation to talk about how quickly the runtime grows.
2. relative to the input —With Big O Notation, we use the size of the input, which we call “n”. So we can say things like the runtime grows “on the order of the size of the input” (O(n)) or “on the order of the square of the size of the input” (O(n²)).
3. as the input gets larger — Our algorithm may have steps that seem expensive when n is small but are eclipsed eventually by other steps as n gets larger. For Big O Notation analysis, we care more about the stuff that grows fastest as the input grows, because everything else is quickly eclipsed as n gets very large.

3.

Calculating Time complexity:

• Let say the iteration in Binary Search terminates after k iterations.
• At each iteration, the array is divided by half. So let’s say the length of array at any iteration is n
• At Iteration 1,

  Length of array = n

• At Iteration 2,

  Length of array = n⁄2

• At Iteration 3,

  Length of array = (n⁄2)⁄2 = n⁄22

• Therefore, after Iteration k,

  Length of array = n⁄2k

• Also, we know that after

  After k divisions, the length of array becomes 1

• Therefore

  Length of array = n⁄2k = 1
  => n = 2k
  

• Applying log function on both sides:

  => log2 (n) = log2 (2k)
  => log2 (n) = k log2 (2)

• Hence, the time complexity of Binary Search is

  log₂ (n)

• As (log_a (a) = 1)
  Therefore,

  => k = log2 (n)
  

4.Under what conditions is it possible to sort a list in less than O(nlog n) time?

If the list is already sorted ,it is possible to sort a list in less than O(nlog n) time?