Determining Big O Notation

An easier way

  • (4 Pages)
  • +
  • « First
  • 2
  • 3
  • 4

53 Replies - 117316 Views - Last Post: 02 March 2013 - 05:43 PM Rate Topic: -----

#46 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10188
  • View blog
  • Posts: 37,629
  • Joined: 27-December 08

Re: Determining Big O Notation

Posted 30 July 2011 - 02:24 PM

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. :)
Was This Post Helpful? 2
  • +
  • -

#47 PlasticineGuy  Icon User is offline

  • mov dword[esp+eax],0
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,436
  • Joined: 03-January 10

Re: Determining Big O Notation

Posted 16 August 2011 - 09:41 PM

To help those having issues visualising Big-O notation, here's a visual representation:
Posted Image
Legend
  • Yellow: O(n2)
  • 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(n2) reaches 100.

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

Was This Post Helpful? 2
  • +
  • -

#48 jmsoriano  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 15-March 12

Re: Determining Big O Notation

Posted 06 October 2012 - 05:11 PM

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.

Was This Post Helpful? 0
  • +
  • -

#49 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 06 October 2012 - 05:23 PM

That is correct.
Was This Post Helpful? 0
  • +
  • -

#50 intrepidis  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 08-October 12

Re: Determining Big O Notation

Posted 08 October 2012 - 03:06 AM

What about recursion? How would you find the big-O notation for recursive algorithms?
Was This Post Helpful? 0
  • +
  • -

#51 jmsoriano  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 15-March 12

Re: Determining Big O Notation

Posted 08 October 2012 - 10:21 AM

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
Was This Post Helpful? 0
  • +
  • -

#52 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10188
  • View blog
  • Posts: 37,629
  • Joined: 27-December 08

Re: Determining Big O Notation

Posted 08 October 2012 - 10:55 AM

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.
Was This Post Helpful? 0
  • +
  • -

#53 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Re: Determining Big O Notation

Posted 02 March 2013 - 04:38 PM

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?
Was This Post Helpful? 0
  • +
  • -

#54 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10188
  • View blog
  • Posts: 37,629
  • Joined: 27-December 08

Re: Determining Big O Notation

Posted 02 March 2013 - 05:43 PM

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.
Was This Post Helpful? 0
  • +
  • -

  • (4 Pages)
  • +
  • « First
  • 2
  • 3
  • 4