7

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

Vaibhav
  • 6,082
  • 9
  • 46
  • 71

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
  • 260,367
  • 30
  • 546
  • 667
  • 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