Myujth

I know that Insertion Sort is supposed to be worst case O(n^2), but I'm wondering why the following implementation isn't O(n).

void main()

//insertion sort runs from i = 1 to i = n, thus is worst case O(n)
for (

 int i = 1,
 placeholder = 0,
 A = 10,9,8,7,6,5,4,3,2,1 ,
 j = i;

 i <= 10;

 j-- > 0 && A[j - 1] > A[j]
 ? placeholder = A[j], A[j] = A[j - 1], A[j - 1] = placeholder
 : j = ++i
)


for (
 int x = 0;
 x < 10; x++
) 
 cout << A[x] << ' ';
 cout << endl;



system("pause");

There is only one for loop involved here and it runs from 1 to n. It seems to me that this would be the definition of O(n). What exactly am I missing here?

Thats a very odd way to write code.But You have 2 for loops in the definition. It is not always necessary to have nested loops to have O(n^2), you can have it with recursion also.
In simple terms O(n^2)n simply means number of operations performed when the input size is n.

The code given is not a correct c++ code and not even close to a pseudocode.
The correct code should be like this:

void main()

 int i,j,key;
 int A=10,9,8,7,6,5,4,3,2,1;
 //cout<<"Array before sorting:"<<endl;
 //for(i=0;i<10;i++)
 //cout<<A[i]<<"t";
 //cout<<endl;
 for(i=1;i<10;i++)
 
 key=A[i];
 for(j=i-1;j>=0 && A[j]>key;j--)
 
 A[j+1]=A[j];
 
 A[j+1]=key;
 
 //cout<<"Array after sorting:"<<endl;
 //for(i=0;i<10;i++)
 //cout<<A[i]<<"t";
 //cout<<endl;

See, insertion sort has two loops. Outer loop is to maintain the key variable and the inner loop is to compare the elements prior to key variable with the key variable. And therefore the worst case time complexity is O(n^2) and not O(n), as the basic algorithm of insertion sort contains two loops, both of which eventually iterate n times in case of worst case i.e. when the array is inverted.