CODEWITHSUNDEEP
performancealgorithmcomputation-theorybig-o
Nicomachus
Nicomachus

Reputation: 11

Is Big Theta Notation an efficient measure of algorithm efficiency when the expected input size is small?

I've looked all around for information about Big-Theta, and I think I've come to a decent understanding of it. However, the question remains: Is Big Theta Notation an efficient measure of algorithm efficiency when the expected input size is small?

I'm thinking that Big Theta Notation is not an efficient measure of algorithm efficiency when the expected input size is small. To begin with here's part of my understanding of Big Theta: a function f(n) is Big Theta(n) if it is O(n) and Big Omega(n). The mathematical definition for all of these values requires n>n0. So, according to my reasoning, it is possible(and probable) for a small input size to be less than n0. Therefore, my reasoning is that Big Theta Notation is not an efficient measure of algorithm efficiency for values that n< n0.

Upvotes: 1

Views: 498

Answers (1)

tskuzzy
tskuzzy

Reputation: 36476

That is correct. For small input sizes, the running time could be anything. For example, when sorting a small list of numbers (on the order of ~10 elements), insertion sort is actually one of the fastest algorithms to use despite a quadratic asymptotic run time.

Upvotes: 1

Related Questions