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.)

Answer 1

Please post 5 question as different question,

1.

Big O notation used to determine the performance of an algorithm in the worst-case scenario.
Mathematically :
ƒ(x)={ O(g(x), if there is a x_c where   x₀ ( 1, ) and a k where k is constant such that

ƒ(x)<=k*g(x) for all  x>=x_c   

2. Explain why we use big-O to compare algorithms.

Performance of the algorithm depends on -

1. Way of implementation

2. The number of inputs provided.

big-O notation provide the performance of an algorithm against varying input in the worst case .

That's why we consider the big-O notation

3. Explain why binary search runs in O(log n) time.

In Binary search , search always starts from middle, It checks the conditions whether to go to left or right side. Thus height of tree created is O(logn), and run-time complexity is O(logn)

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

If no of inputs to sorted is know and also maximum value in the input is known, It can be sorted in O(n) time complexity where n is the maximum element in the input.

example Bucket sort