a) Why do we use asymptotic analysis over experimental analysis? What case do we

Question

a) Why do we use asymptotic analysis over experimental analysis? What case do we most often consider, why don’t we typically consider the others? Answer in 2-3 sentences for each question..

b) What are the two types of Big-O performance we went over in lecture? What do they mean? Answer in 2-3 sentences.

c) What is the Big-O performance of the following operations?

   i) Searching through a Singly Linked List for an arbitrary value.

   ii ) Searching through a fixed array for an arbitrary value.

   iii) Getting the element of the i-th position in a Singly Linked List.

   iv) Getting the element of the i-th position in a fixed array.

   v) Getting the last element of a Doubly Linked List.

Explanation / Answer

a) Why do we use asymptotic analysis over experimental analysis? What case do we most often consider, why don’t we typically consider the others? Answer in 2-3 sentences for each question..

Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst case scenario of an algorithm.

Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded to work in a constant time. Other than the "input" all other factors are considered constant.

b) What are the two types of Big-O performance we went over in lecture? What do they mean? Answer in 2-3 sentences.

Big O Notation: The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.

(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) c.g(n) for all n > n0. }

Little asymptotic notation

Let f(n) and g(n) be functions that map positive integers to positive real numbers. We say that f(n) is (g(n)) (or f(n) (g(n))) if for any real constant c > 0, there exists an integer constant n0 1 such that f(n) 0.

Its means little o() means loose upper-bound of f(n).

c) What is the Big-O performance of the following operations?

i) Searching through a Singly Linked List for an arbitrary value.

Ans: O(n)

ii ) Searching through a fixed array for an arbitrary value.

Ans: O(n)

iii) Getting the element of the i-th position in a Singly Linked List.

Ans: O(n)

iv) Getting the element of the i-th position in a fixed array.

Ans: O(1)

v) Getting the last element of a Doubly Linked List.

Ans: O(1)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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