# Determining Big O Notation

## An easier way

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

## 54 Replies - 306414 Views - Last Post: 06 September 2019 - 09:53 AMRate Topic:     1 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=125427&amp;s=fdbe894d32ccc11319b0044f28bc9ab3&md5check=' + ipb.vars['secure_hash'], cur_rating: 5, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #46 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12769
• Posts: 45,951
• 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 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 Reputation: 3212
• Posts: 19,240
• Joined: 14-September 07

## Re: Determining Big O Notation

Posted 06 October 2012 - 05:23 PM

That is correct.

## 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: 12769
• Posts: 45,951
• 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.

## 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: 12769
• Posts: 45,951
• 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.

### #55 enigma369 Reputation: 0
• 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! Manh, this is so easy, I can now calculate the big (stupid) O of any function because of your explanation! I loved it! [Thanks a ton a million for sharing your knowledge in easy understandable words.! • (4 Pages)
• • « First
• 2
• 3
• 4

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }