# My accepted answer in java, is it cost O(n) or O(n^2)???

• I use a StringBuffer, I don't know whether the method deleteCharAt() cost O(1) or O(n).

``````    public class Solution {
public String getPermutation(int n, int k) {
if(n > 9) return"";
if(n == 1) return "1";
int [] num = new int[n+1];
num[0] = 1;
for(int i = 1;i<=n;i++)
num[i] = num[i-1]*i;    // store the factor
k = k-1;
k = k%num[n];
StringBuffer numStr = new StringBuffer("123456789");
StringBuffer res = new StringBuffer();
for(int i=n-1;i>=0;i--)
{
int curNum = k/num[i];
res.append(numStr.charAt(curNum));
numStr.deleteCharAt(curNum);
k = k - curNum*num[i];
}
return res.toString();
}
}``````

• Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.

• Time complexity is neither O(n^2) nor O(n), due to a single reason that the input number n is fixed in between the range [1,9]. String Buffer deleteCharAt() has amortized constant time.

• The delete operation is O(n), so it makes your algorithm O(n^2). It doesn't affect a lot because n wont grow larger than 15 otherwise k will overflow the capacity of int.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.