Like Tree4Likes
  • 1 Post By überfuzz
  • 3 Post By whiteflags

STL string::find - complexity O(?)

This is a discussion on STL string::find - complexity O(?) within the C++ Programming forums, part of the General Programming Boards category; I've seen different numbers of the complexity of this function. With a short string as a needle and a long ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    110

    STL string::find - complexity O(?)

    I've seen different numbers of the complexity of this function. With a short string as a needle and a long string as haystack a worst case is clearly O(n) and a best (1).

    My question, I've also seen O(log n), how is this complexity calculated or derived?

  2. #2
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Quote Originally Posted by überfuzz View Post
    I've seen different numbers of the complexity of this function. With a short string as a needle and a long string as haystack a worst case is clearly O(n) and a best (1).

    My question, I've also seen O(log n), how is this complexity calculated or derived?
    Ah I get it, it is wrong. The log n complexity is for binary trees. An average complexity for a string search like the one I proposed the complexity is O(n/2).

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Yeah except that you drop the /2 when talking about Big-Oh notation.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Ops, I shouldn't post when I'm drunk. Sorry!
    Lesshardtofind likes this.

  5. #5
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    407
    I've made that mistake a few times. I would rather post while drunk then wake up to a mess I coded the night before while drunk.

  6. #6
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,423
    Or, you know, you could stop getting drunk in the first place!
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    Yes, mom.
    Neo1, laserlight and Elkvis like this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 11-23-2012, 11:31 PM
  2. Find index of last char in search string in string?
    By Programmer_P in forum C++ Programming
    Replies: 6
    Last Post: 06-07-2010, 06:51 PM
  3. std::string::find vs std::find
    By petry in forum C++ Programming
    Replies: 17
    Last Post: 07-08-2009, 05:26 PM
  4. find a string based on the location of another string
    By rlilley in forum C Programming
    Replies: 3
    Last Post: 02-19-2009, 11:29 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21