### Thread: Is this algo O(n) or O(log n)?

1. #### 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 low-degree constants (so in this case, 1/2 * n should become just n), but this value is not necessarily always 1/2 of n.
2. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1313
n/2 is not O(log(n)).
3. 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 worst-case for evaluating (in this case, O(n)), correct?
4. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1313
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.
5. 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?
6. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1313
Yes, that's Theta(n) (and hence also O(n), but Theta(n) is more informative), and thus not O(log(n)).
7. Ok, thank you! Sorry I was a bit vague by the by.