Thread: efficiency

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    5

    efficiency

    i know this is no c++ question, can any one tel me:
    in efficiency class is log2^n the same and log3^n or logx^n, because we can change base right?

    thanks in advance .

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    Are you talking about "BigO"?

    If so, yes, because constant factors are abstracted away because they don't affect growth potential.

    (Unless you are taking about trying to make a O(logN(N)) algorithm look like something it probably isn't.)

    Soma

  3. #3
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    ... and why it's not even usually spelled as O(logn^n), but simply O(log n)
    Last edited by Mario F.; 06-14-2011 at 03:15 PM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    log[a](N)=log[b](N)/log(a).

    So if you have a bunch of functions that have a log term of any base, you can convert them to functions of a log term of your favorite base, with a constant product. Constant products are ignored in O(N) notation, so it doesn't matter what base is used; they are all comparable, as long as it is greater than 1.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Check for efficiency
    By rgrwatson85 in forum C Programming
    Replies: 8
    Last Post: 02-28-2011, 09:27 PM
  2. Efficiency with c++
    By pastitprogram in forum C++ Programming
    Replies: 17
    Last Post: 08-08-2008, 11:18 AM
  3. std::vector efficiency
    By Ancient Dragon in forum C++ Programming
    Replies: 2
    Last Post: 12-15-2005, 01:43 PM
  4. Validation efficiency
    By subdene in forum C++ Programming
    Replies: 6
    Last Post: 07-23-2004, 04:54 PM
  5. Looking for efficiency in my app
    By dead_cell in forum C++ Programming
    Replies: 7
    Last Post: 07-01-2002, 10:22 PM