#1
  1. A94528C464D168DC82FE4933E9DF37
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Location
    California
    Posts
    119
    Rep Power
    73

    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. #2
  3. 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)).
  4. #3
  5. A94528C464D168DC82FE4933E9DF37
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Location
    California
    Posts
    119
    Rep Power
    73
    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?
  6. #4
  7. 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.
  8. #5
  9. A94528C464D168DC82FE4933E9DF37
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Location
    California
    Posts
    119
    Rep Power
    73
    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?
  10. #6
  11. 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)).
  12. #7
  13. A94528C464D168DC82FE4933E9DF37
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Location
    California
    Posts
    119
    Rep Power
    73
    Ok, thank you! Sorry I was a bit vague by the by.

IMN logo majestic logo threadwatch logo seochat tools logo