Determining Big O Notation

An easier way

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

54 Replies - 299929 Views - Last Post: 06 September 2019 - 09:53 AM Rate Topic: ***** 1 Votes

#46 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12657
  • View blog
  • Posts: 45,830
  • 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   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   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   User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3202
  • View blog
  • Posts: 19,235
  • 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   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   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   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12657
  • View blog
  • Posts: 45,830
  • 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   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   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12657
  • View blog
  • Posts: 45,830
  • 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
  • +
  • -

#55 enigma369   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 06-September 19

Re: Determining Big O Notation

Posted 06 September 2019 - 09:53 AM

This is amazing!!! At first I was afraid of the discrete algebraic formulae for calculating the asymptotic notations of algorithms or functions. I mean just by thinking of all these heavy smarty words feels huge thing. I needed to learn this at any condition in order to perform at my assignment. Guess what, a blessing came along and I stumbled upon this post! :genius: Manh, this is so easy, I can now calculate the big (stupid) O of any function because of your explanation! I loved it! :angel: [Thanks a ton a million for sharing your knowledge in easy understandable words.! :flowers:
Was This Post Helpful? 0
  • +
  • -

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