@Arjun Sir, after seeing the question,my approach was like:
For 1st search, the number of comparisons would be O(n).
For 2nd search, the number of comparisons will be O(n-1) since now, 1 element has been decreased from the array.
Similarly, the searches would continue in the form of O(n)+O(n-1)+O(n-2)+O(n-3)+........+1=O(n^2).
So, for 100,000 searches, Total comparisons= (n^2)*100,000
Given, n=1000,000, so, Total Comparisons= 100,000 *100,000 *100000=10^15.
Kindly guide me where am I going wrong since this is not the answer. :(