CODEWITHSUNDEEP
algorithmtime-complexity
bts
bts

Reputation: 33

Time complexity for constant length loop

I am having a hard time deciding how to state the worst-case runtime complexity of a function within a class.

This class stores two kinds of objects, say N and M, possibly millions of them.

One of the operations just searches for the best place to store an item:

void foo(item) {
    for (int i=0;i<K;i++) {
        for (int j=i;j<K;j++) {
            if(store(i,j,item)) // store is O(1)
                return;
        }
    }
}

Here K, is a problem defined constant (say 10). In the worst case the item might not be stored and the loops will be exhausted.

I can't decide if it's more correct to say foo has O(1) complexity, as K is a given constant that doesn't depend on N and M; or it's better to say complexity is O(k2). Maybe even amortized O(1) ?

Upvotes: 3

Views: 2105

Answers (2)

user1196549
user1196549

Reputation:

It is more informative and harmless to say that the complexity is O(K²). Then, knowing that K is bounded, you would implicitly conclude that this is O(1).

In practice, the hidden constant being 5 or 5000000 makes a difference.

Upvotes: 3

amit
amit

Reputation: 178491

K is a given constant that doesn't depend on N and M

Note that the first and last part of the sentence are not self-contradicting.

If k doesn't depend on M,N - it does not mean it does not independently grows. If it does grow (does not matter in what rate), of is a parameter of your function - the complexity depends on it and is indeed O(k^2).

If k is constant and never changes, this is indeed O(1), because k^2 < C for some constant C=k^2+1.

Common examples of usage of constant values in iterations are:

  • Going over a finite size alphabet when doing strings algorithms (trie for example)
  • Going over bits of fixed integers.

These are regarded as O(1), even though they are implemented with a loop, what matters is - the time processing the loop is bounded by a finite size.

Upvotes: 3

Related Questions