[macosxnerd101]

Quote

Binary search will always be more efficient ten a linear search if the data is sorted.

Just to clarify, as long as the context is an array or binary search tree. With Linked Lists, binary search comes out to O(n log(n)). I'm nitpicking a little at this point, though.

[PlasticineGuy]

To help those having issues visualising Big-O notation, here's a visual representation:

Legend

• Yellow: O(n²)
  
• Red: O(n)
  
• Cyan: O(n log n)
  
• Green: O(log n)
  
• Blue: O(1)

I found O(log n) and O(n log n) to be most difficult to understand. This graph shows us that O(log n) starts out slower than O(n), but as n increases it becomes much faster. O(n log n) starts out faster than O(n) but at n = 10 it outstrips O(n).

Note: My software is unable to plot O(n!). However, by n = 10 it reaches 3 628 800, whereas O(n²) reaches 100.

This post has been edited by PlasticineGuy: 16 August 2011 - 09:50 PM

[jmsoriano]

Any help greatly appreciated

  // first nested loop
            for (cnt1 =0, i = 1;i <= n; i++) //linear
                 for (j = 1; j <= n; j++) //linear too
                       cnt1++;
            // second nested loop 
             for (cnt2 =1, i =0;i <= n; i++) //linear
                 for (j = 1; j <= n; j++) //linear too
                       cnt2++;

/* I thins this two are the same, both are O(n*n) or O(n^2), is this a correct assumption
    I think the teacher gave us two of the same to confuse the crap out of us.

[KYA]

That is correct.

[intrepidis]

What about recursion? How would you find the big-O notation for recursive algorithms?

[jmsoriano]

int selectkth(int a[], int k, int n){
	int i, j, mini, tmp;
	for (i = 0; i < k; i++) { // linear = O(k);
		mini = i;
		for (j = i+1; j < n; j++) // linear also O(n)
			if (a[j]<a[mini])
				mini = j;
		tmp = a[i];
		a[i] = a[mini];
		a[mini] = tmp;		
	}
	return a[k-1];
}

/*  The outer loop executes k times, the inner loop executes (n^2/2  - 1/2) times
	because of the if statement in the inner loop
	after summation we have that: T(n) =  c + k*(n^2/2 - 1/2)
	dropping lower terms we have O(k*n^2) */ 

This one is tricky.
I think I got it wrong, will you please let me know where this is wrong ?
Thanks

[macosxnerd101]

As far as the algorithm goes, k still has to be bounded by n. So this algorithm is O(n^2).

Quote

What about recursion? How would you find the big-O notation for recursive algorithms?

If it's mathematical recursion, you can set up a recurrence relation and use the formal definition of Big-O to find a good g(n) function so that f(n) (your recurrence) is O(g(n)). If it isn't mathematical (maybe a sorting algorithm instead), you will have to work to find a T(n) function to model runtime complexity. As you continue, you usually end up finding a recurrence relation to solve anyways. I found this link which goes a little more into algoirthm analysis of recursive algorithms.

[medaa]

def comeTogether(table1, table2):
i=0
table3=[]
while i<len(table1) and i<len(table2):
table3.append(table1[i]+table2[i])
i+=1
j=i
while i<len(table1):
table3.append(table1[i])
i+=1
while j<len(table2):
table3.append(table2[j])
j+=1
return table3

How come for this the big-o is O(n+m) not O(n), is it because theres two arguments?

[macosxnerd101]

That is correct. There are two independent variables that affect the runtime. If your focus is on m, then it is completely correct to say that this algorithm is O(m). This ignores the fact that n can vary as well.