7

I wanted to know the time complexity of the next_permutation function. Can I view its code too ?

Vaibhav
  • 6,620
  • 11
  • 47
  • 72

1 Answers1

12

See http://www.sgi.com/tech/stl/next_permutation.html:

Linear. At most (last - first) / 2 swaps.

To see the source code, just look in STL header files for your system. On a Unix-like system, you probably need to look somewhere like /usr/include/c++/4.1.2/bits/stl_algo.h.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
  • 3
    Actually, it's better than linear. It's amortised O(1) — i.e., if you call it n! times, it takes only O(n!) operations, not n*n!. See [this question](http://stackoverflow.com/questions/4973077/the-amortized-complexity-of-stdnext-permutation). – ShreevatsaR Jun 30 '11 at 11:58