Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am going through some CS basics and the documents says in places that:

We need the run time to be at least logarithmic.

What does that mean?

By def, log means:

The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number.

What does it truly mean when we say we want a run time to be logarithmic?

share|improve this question
1  
At least logarithmic means $f(n)\ge C\log n$ for some $C$. –  anon Jul 7 '12 at 10:31
1  
This is also written in CS literature as $f(n)\in\mathcal{O}(\log(n))$ –  Shaktal Jul 7 '12 at 10:44
3  
anon's and Shaktal's comments disagree; $f(n) = O(\log n)$ would mean $f(n) \le C\log n$ for some $C$ (and all sufficiently large $n$). But I think Shaktal's is the more likely interpretation; it's rare to want an algorithm to be slower than something, but it's common to want it to be "at least as good as" something. –  Rahul Jul 7 '12 at 10:49
    
I would assume "at least" logarithmic means that a function grows equal to or faster than logarithms, but the others are right that the opposite interpretation makes more sense in the context of computer science (where generally we want programs to be as efficient as possible). Weird. –  anon Jul 7 '12 at 11:52
add comment

1 Answer

up vote 3 down vote accepted

Your question has two answers (although one is considerably more likely).

Firstly, the author could mean that the running time must be slower or as slow as some $C\log{n}$ (as pointed out by anon in the comments), i.e:

$$f(n)\ge C\log{n}\implies f(n)\in\mathcal{\Omega}{(\log{n})}$$

This means that given some set of $n$ inputs, the algorithm will complete no faster than $C\log{n}$, for some arbitrary constant $C\in\mathbb{R}^{+}$.

However, as you have stated it is a piece of CS literature, what is more likely is that the author intended that the algorithm would complete faster or as fast as some $C\log{n}$, i.e:

$$f(n)\le C\log{n} \implies f(n)\in\mathcal{O}{(\log{n})}$$

This means that the algorithm, given a set of $n$ inputs as before, will complete no slower than $C\log{n}$, for some arbitrary constant $C\in\mathbb{R}^{+}$.

Bear in mind that we often use asymptotic notation (e.g. $f(n)\in\mathcal{\Omega}(\log{n})$, $f(n)\in\mathcal{O}(n^{2})$) in computer science to approximate the running time of algorithms. Also note that $f(n)\in\mathcal{O}(n)$ could also be written as $f(n)=\mathcal{O}(n)$ (indeed this notation is more common in CS literature).

Hope this helps clear things up!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.