Determining Big O Notation

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

53 Replies - 241310 Views - Last Post: 02 March 2013 - 05:43 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=125427&amp;s=b053ec560786dea21065d59649116922&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#46 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11789
• Posts: 44,298
• 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.

#47 PlasticineGuy

• mov dword[esp+eax],0

Reputation: 281
• 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:

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

#48 jmsoriano

Reputation: 0
• 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.
```

#49 KYA

• Wubba lubba dub dub!

Reputation: 3186
• Posts: 19,211
• Joined: 14-September 07

Re: Determining Big O Notation

Posted 06 October 2012 - 05:23 PM

That is correct.

#50 intrepidis

Reputation: 0
• 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?

#51 jmsoriano

Reputation: 0
• 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

#52 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11789
• Posts: 44,298
• 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.

#53 medaa

Reputation: 6
• 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?

#54 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11789
• Posts: 44,298
• 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.