### BubbleSort Complexity

I'm a little confused. I know that the complexity of BubbleSort is (n(n+1))/2 , but my question is:

Suppose I have an array, I understand how passes work - but If I need to find the "theoretical search statistics" would I just count how many passes I have and then plug the # of passes into "n"?

 ``12345678910111213141516171819202122232425262728293031323334`` ``````#include using namespace std; int main() { int arrTest[] = {22, 33, 101, 12, 40}; bool sorted = false; bool swapped = false; for (; !sorted ;) { swapped = false; for (int i = 0; i < 4; ++i) { if (arrTest[i] > arrTest[(i + 1)]) { int buff = arrTest[i]; arrTest[i] = arrTest[(i + 1)]; arrTest[(i + 1)] = buff; swapped = true; } } if (!swapped) sorted = true; } for (int j = 0; j < 5; ++j) { cout << arrTest[j] << endl; } getchar(); return 0; }``````

Test this out and see, although you should try playing around, see what happens when you change things around, or add in user input for the array.
Is getchar(); some kind of pre-defined library function? It's acting like it's not declared in the scope. What library should I include? By the way I am working with PuTTy
I got it to work, but this algorithm isn't really helping me. See, I already understand how Bubble Sort works. I need to understand WHAT i would plug into the value of n. I also need to find out which formula to use..Worst Case,Best Case,Average Case, or its On the order notation.
n is the amount of elements you are sorting.
 I also need to find out which formula to use..Worst Case,Best Case,Average Case
That depend on what do you need. I believe names are self-descriptive.

O(n) notation is used when you need asymptotic complexivity or the order of magnitude of how execution time depends on number of elements when n → ∞
Thank you! Well I'm not sure which I need because it just says to calculate the Theoretical sort statistics...I'm so confused.. Would that just be the general formula of Bubble Sort which would be what?
I believe you will need average case: it is statistical average of multiple runs on random data.
Thank you so much for your help! So I would just take the amount of elements I am sorting which I can call as "n" and then plug them in to the average case which is n^2? So, if I had 3 elements 1 3 2 , I would have actual sort stats: 3, and theoretical sort stats: 9 correct?
It is asymptotical values. They are not representative on small values.
So are you saying that I would not be able to find the average case if I had only 2 elements? I don't understand...what does n have to be greater than for me to use the theoritical sort stats?
nvm, i figured it out.
Topic archived. No new replies allowed.