Sereche
Profile Answers by Sereche

Jul 9th, 2012
This seems to be a question about time complexity / big-O notation. Time complexity basically tells you how the program running time scales, as a function of one of the variables of input (in most cases, the size of the input). Your first function (the binary search) runs in O(log n) time, the second runs in O(n) time. What this means is best illustrated with an example:

Lets say that running your binary search function on an array of 1,000 elements takes, on average, 1 second. You would then expect the function to take about 2 seconds to run on an array of 1,000,000 elements, and about 3 seconds on an array of 1 billion elements. Similarly, with an O(n)-time algorithm, you would expect the running time to roughly double when you double the size of the input set.

Note that these estimates are just that, estimates. At low values of n, the information is almost meaningless, as overhead costs become a larger factor. In addition, not all O(n) algorithms will run in the same amount of time, though, for large enough n, those times should differ by a constant factor (i.e. one O(n) algorithm takes roughly twice as long as a different O(n) algorithm).

For more information on time complexity, I would recommend reading http://en.wikipedia.org/wiki/Time_complexity.

Also, note that the code youve provided is not valid C (or, for that matter, any language that I can recognize). The public/static qualifiers are meaningless in C (C#, maybe?). Passing an array as a parameter is not done correctly (and is typically not done at all in C or C++; again, did you mean C#?). Since youve tagged this question as C++, and put C in the title, Ive included code which should be valid in both C/C++. (Note: I havent actually tested it, so there is always the possibility of some small error)
Code
span style="font-style: italic;">//Note that the following three lines can be replaced with


   // cin >> x;


   //if you are writing in C++ //Again, these three lines can be replace with cin in C++

C Coding question on running time program

/*assume contents are sorted*/
Public static intbinarySearch(int x,int a[]){
int low=0; 0(1)
int high=a.length-1; 0(1)
int mid; 0(1)

while(low<=high){
mid=(low+high)/2
if(a[mid]low=mid+1;
else if(a[mid]>x)
high=mid-1;
else
return mid;
}
return -1;
}

---------------------

n=0 0(1)
sum=0; 0(1)
cin>>x;
while(x!=99)
{
n++; 0(1)
sum+=x; 0( n/x)
cin>>x;
}
mean - sum/n;

what is the running time?
Please help me understand it. The websites are not that helpful to me. Please. Please if you're not that busy can you please answer it with explanations?:) :) :) THANK YOU!!