STL set max element in O(lgN)

This is a discussion on STL set max element in O(lgN) within the C++ Programming forums, part of the General Programming Boards category; Hello Is it possible to find max element in STL set with complexity O(lgN) ?...

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    6

    STL set max element in O(lgN)

    Hello

    Is it possible to find max element in STL set with complexity O(lgN) ?

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
    *set.rbegin();
    This should do the trick in constant time.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    6
    Right, thank You... heh that was so easy

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Code:
    max = *set.rbegin();
    for (int i = 0; i < log(set.size()); i++) { 
        max = *set.rbegin();
    }
    return max;
    there it is, log(n) time as requested

  5. #5
    Registered User
    Join Date
    Apr 2008
    Posts
    6
    Mhm thanks, but I think I will stick with O(1)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. rearrange the value in a given set from max to min
    By Downnin in forum C++ Programming
    Replies: 14
    Last Post: 07-17-2005, 11:31 AM
  2. Set Classes
    By Nicknameguy in forum C++ Programming
    Replies: 13
    Last Post: 10-31-2002, 01:56 PM
  3. Set Classes
    By Nicknameguy in forum C++ Programming
    Replies: 3
    Last Post: 10-21-2002, 07:40 PM
  4. Binary searches
    By Prezo in forum C Programming
    Replies: 4
    Last Post: 09-10-2002, 09:54 PM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

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