Calculating running time of a program (Big O Notation)

Let's say the input to foo is:

foo(array, 0, 1000) 

So, first of all, x becomes 200 which is one fifth of the whole data. Then y and z become the second and the fourth quintiles. Note that they are still a fraction of end - start (1000), not constants.

The for goes:

for(index = y; index < z; index++) 

which is from y to z. y was 400 (2 * 1000 / 5) and z was 800 (4 * 1000 / 5). So the number of times the for loops is 800 - 400 = 400 = (4 - 2) * 1000 / 5. Perhaps the person who analyzed this for you called it N, but it's quite absurd. What you do inside the loop is a simple increment which takes constant time (O(1)) and there is no N involved there!

So let's name things ourselves. I'll call the 1000 above N. So basically, the for loops 2N/5 times.

How about the recursions? The first recursion recurses on start to start + x (i.e. the first 2/5 of the data) and the second one recurses on start + z to end (i.e. the last 1/5 of the data).

Assuming your function takes f(N) time in total to calculate whatever it is doing, it can be broken down to:

f(N) = f(2N/5) + 2N/5 + f(N/5) 

Now all you need is to analyze this recursive function and try to understand what would be the order.

While there are many ways to understand this, such as drawing a tree that shows how f expands and with what parameters, you can also try to find the easier upper and lower limits of the function. If they are the same, you're in luck:

2N/5 + 2*f(N/5) < f(n) < 2*f(2N/5) + 2N/5 

By the master theorem, both limits fall in Case 3, and both limits turn out to be θ(N), so your foo function is in fact θ(N).

Another way too look at it is the following:

1. The first recursion touches the first 2N/5 of the data
2. The for loop touches the second 2N/5 of the data
3. The second recursion touches the last N/5 of the data

As you can see, each element of the array is touched once and only once. So the time complexity of the function is θ(N).

Before we look at the actual Big-O of the function as a whole, let's correct your code snippet real quick.

// O(4 + N + 2*O(?)) = O(N + O(?)) void foo(float[] array, int start, int end){ if((end-start) <=1) return; // O(1) int x = (end-start) / 5; // O(1) int y = 2*x; // O(1) int z = 4*x; // O(1) foo(array,start,start+y); // O(?) for(index = y; index < z; index++){ // O(N) array[index]++; // O(1) } foo(array, start+z, end); // O(?) } 

Now, in the base case (end - start <= 1), foo returns immediately, making it O(1). In the second to base case, that means that this function is O(N) (just the for loop). In the third to the base case, that means that this function is O(N + N + N) = O(3N) = O(N). It proceeds this way up the chain.

It's important to remember that there's some (possibly large) constant factor there that we're ignoring, but the algorithm as a whole still falls into the category of O(N).

Admittedly, this method lacks rigor, but gets us a good estimate with a minimum of work.