CODEWITHSUNDEEP
algorithmtime-complexity
unj2
unj2

Reputation: 53501

What does O(log(log(n))))-competitive mean?

I was going through some data structures and I noticed this as a time complexity: O(log(log(n))))-competitive.

I read that constant-competitive was the ratio of the expected time/optimal time. But what does it mean to have a set-competitive?

Upvotes: 10

Views: 5569

Answers (2)

kanak
kanak

Reputation: 156

Online algorithm is one which does not know its inputs in advance, and must "react" (in a sense) to unpredictable inputs. In contrast, offline algorithms are those which know all its inputs in advance.

Competitive analysis compares the performance of an optimal online algorithm to an optimal offline algorithm. Thus, k-competitive means that there is an offline algorithm which performs at most k-times worse than an online algorithm. So, O(lglgn) competitive means that the optimal offline algorithm performs at most lglgn (times a constant) times worse than the optimal online algorithm.

The term "k-competitive" can be thought of in the same manner as the term "k-approximation". A k-approximation means that the approximation algorithm performs at most k times worse than the optimal algorithm.

Upvotes: 14

Nick Dandoulakis
Nick Dandoulakis

Reputation: 43130

This can shed some light on your question.

From the above link:

Let A be any BST algorithm, define A(S) as the cost of performing sequence S and OPT(S, To) as the minimum cost to perform the sequence S. An algorithm A is T-competitive if for all possible sequences S, A(S) <= T * OPT(S, To) + O(m, n).

Upvotes: 1

Related Questions