February 26th, 2010, 01:49 AM

Is this algo O(n) or O(log n)?
I just wanted to know if I have written an algorithm who has at most n operations and at least n/2 operations, does this qualify as O(log n)?
I know that when figuring out the complexity, you are supposed to drop all lowdegree constants (so in this case, 1/2 * n should become just n), but this value is not necessarily always 1/2 of n.
February 26th, 2010, 02:02 AM

February 26th, 2010, 02:30 AM

I know n/2 is not O(log n), but again, I'd like to reiterate that the algorithm is only conditionally n/2.
So I would then be best off using the worstcase for evaluating (in this case, O(n)), correct?
February 26th, 2010, 11:37 AM

I have no idea what you're asking. You stated that the complexity is at least n/2 and at most n, which is clearly Theta(n), and not O(log(n)). I'm not sure if this is your confusion, but O(f(n)) means the worst case is no worse than c*f(n) for some constant c that doesn't depend on the problem.
February 26th, 2010, 12:01 PM

Originally Posted by Lux Perpetua
I have no idea what you're asking. You stated that the complexity is at least n/2 and at most n, which is clearly Theta(n), and not O(log(n)). I'm not sure if this is your confusion, but O(f(n)) means the worst case is no worse than c*f(n) for some constant c that doesn't depend on the problem.
Pardon the ambiguity, I suppose I'll just be more specific here.
This is my basic algorithm:
Code:
Input letters
while letters.length > longest_substring.length {
current_substring.concatenate(letters.firstCharacter)
if (letters.firstCharacter > letters.secondCharacter) {
if (current_substring.length > longest_substring.length) longest_substring < current_substring
current_substring.empty()
}
letters.removeFirstCharacter()
}
Output longest_substring
In essence, the algorithm attempts to find the longest sorted substring of letters in a string of letters.
So for a string of length n, it takes at most n iterations and at least n/2 iterations.
So then this would be represented by O(n), not O(log n), correct?
February 26th, 2010, 08:28 PM

Yes, that's Theta(n) (and hence also O(n), but Theta(n) is more informative), and thus not O(log(n)).
February 27th, 2010, 12:53 AM

Ok, thank you! Sorry I was a bit vague by the by.