complexity Big O notation

[Lim Boon Jye]

for my this permutation function and using a loop

//Permutation recursive function
void string_permutation( string& orig, string& perm ,ofstream &outFile){   

	//If empty string will display the permutation
    if( orig.empty() ){
        cout << perm << endl;
		outFile << perm << endl;
        return;   
    }   
   
    for( int i = 0 ; i < orig.size() ; ++i ){   
        string orig2 = orig;   
   
		//erase the alphabet
        orig2.erase(i,1);   
   
		//Use another variable to call the recursive function
        string perm2 = perm;   

		//Get back position for original
        perm2 += orig.at(i);   
   
        string_permutation( orig2 , perm2 , outFile );//Recursive function   
   
    }    
}  

can someone tell me i'm using the function of
O(n) or?
other complexity?

not really know how to differentiate for my this recursive function..

[writetonsharma]

when finding complexity, generally its the loops which are counted and constant expressions are discarded.
so, broadly it would be O(n) as you said.

But if you want to find tune and take constants in consideration, you have to look what is the time complexity of other functions you used inside the loop, like string::at, string::erase etc..

for non critical code, just considering the loops would be good.

[Lim Boon Jye]

but i thought recursive function will be another big-o-notation?

so for my this answer
the answer will be
O(n) ?

[keskiverto]

The first call does N calls in a loop. Each of those does N-1 calls in their loops. The next level does N-2 calls, and so forth. That does sound like a lot more than linear.

[Lim Boon Jye]

ya. i know.
so your mean is that is different N

each N got O(n) right?

so that final answer is what eh.

[ResidentBiscuit]

The way to tell if something O(n) is to double the data set and see if it doubles the amount of calculations. If not, it's not O(n).

[MiiNiPaa]

I would say it looks like O(n²), if all string operation have constant complexivity.

[Lim Boon Jye]

but now mine 1 is a value

i * i

as miiniPaa said .
isn't O(n ^2 ) ?

but this seem like more sense with it

[ResidentBiscuit]

Now that I've actually looked at this, I would say O(n!). AFAIK, finding all permutations will always be O(n!). It's not a speedy operation.

[Lim Boon Jye]

err.
mean this might take long time to take result.
i mean compare with other big o notation
if not mistaken

O(n!) is the slowest 1..

[ResidentBiscuit]

This is why discrete math is a thing. To handle issues like this. Most of the time in the real world, finding all permutations of something just isn't feasible.

[writetonsharma]

That was for one iteration of the function. You will have to add all the iterations. So, lets say it will recur 10 times, so, it will be 10n.

removing the constant will leave you with only a 'n'.

[Lim Boon Jye]

aa like that
@writeton

your answer is
O(n)

quite confuse . why every people not same answer d

[MiiNiPaa]

I was wrong and ResidentBiscuit right. I really didn't look into it.

Saaume, that size of string is N;
When you call your function and loop will execute N times. Each time it will call your function with lenght of N-1; each of that call will loops N-1 times — N·(N−1) loops now. Each of level 2 loops will call function with lenght of N-2 — N·(N−1)·(N−2) loops. And so on in the end we have N·(N−1)·(N−2)·...·3·2·1 loops or N! loops. Each of those loops has constant complexivity and so total complexivity is O(N!)

[Lim Boon Jye]

i have to learn this complexity hard.

for me i think not relaly everyone can master it right?
thanks for u guys for helping me

[MiiNiPaa]

It is just a math. If you good at math, you will learn it at some moment. If you are not, it could be hard.

[writetonsharma]

read concrete maths by D Knuth, if you really want to understand.