CODEWITHSUNDEEP
algorithmbig-ocomplexity-theory
Jerry Spring
Jerry Spring

Reputation: 11

Finding Big O notation when given an array's size range

In one of my CS classes we went over the Big O notation. For a loop like the following the big O would be O(n).

for (int i = 0; i < n; i++) { // code for something here}

This loop is O(n) since n's size is unknown, but what if you knew the size range of n? Say for example you know the passed in array can have a size from 1 to 10 and nothing else. Would the O(n) for the loop above still be O(n), or would it change to be O(1)?

Upvotes: 1

Views: 498

Answers (1)

Arya McCarthy
Arya McCarthy

Reputation: 8829

Big O is about how the complexity of a problem scales with the size of the input. In your case, the size of the input doesn't change. Because of that, it seems appropriate to call it O(1).

An example of when this comes up is when you approximate a computation that requires global information. You may approximate this with local information (only the past K words, or the K nearest nodes in your graph, or your case of a fixed array length) instead of all n items.

K can be quite large, but in terms of asymptotics it's ignored—because it's fixed. To remind people of this, it's common to still write O(K). Note that for any constant K, the set of functions in O(K) is exactly the same as the set of functions in O(1).

Upvotes: 2

Related Questions