# Big Oh Notation Algorithm

Page 1 of 1

## 5 Replies - 1540 Views - Last Post: 20 November 2011 - 06:31 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=256518&amp;s=cb059c1c2e34f5ca3447ec960879c00a&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 volvera215

Reputation: 0
• Posts: 37
• Joined: 08-March 11

# Big Oh Notation Algorithm

Posted 20 November 2011 - 05:03 PM

Hello, I am very new to the concept of creating efficient algorithms and all the angles behind them. One of which is the Big Oh Notation.

I am having some difficulty solving this question relating to Big Oh. Any help would be greatly appreciated. I have not placed in java code yet. Below is the question:

Consider the following two loops:

// Loop A
for (i = 1; i <= n; i++)
for (j = 1; j <= 10000; j++)
sum = sum + j;

// Loop B
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
sum = sum + j;

Although Loop A is O(n) and Loop B is O(n^2). Loop B can be faster than Loop A for small values of n. Design and implement an experiment to find a value of n for which Loop A is faster.

Is This A Good Question/Topic? 0

## Replies To: Big Oh Notation Algorithm

### #2 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: Big Oh Notation Algorithm

Posted 20 November 2011 - 05:12 PM

well for A, the outer loop will execute n+1 times (the last one is to check the condition), and the inner will execute 10001 times. The summation statement will be executed 10000*n times. Similary for loop B the summation will be done n*n times. For small values of n n*n will be much less than 10000*n. So to show an example for which A is faster, just pick a large enough value of n, to make sure that its faster you can setup a test bench and play around.

### #3 volvera215

Reputation: 0
• Posts: 37
• Joined: 08-March 11

## Re: Big Oh Notation Algorithm

Posted 20 November 2011 - 05:15 PM

Can you provide an example please?

Could I use 100 for n? OR does it have to be larger than 10000? OR 10001?

### #4 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: Big Oh Notation Algorithm

Posted 20 November 2011 - 05:29 PM

think .. if n is 100, do you think A will be faster or B, and why?

### #5 volvera215

Reputation: 0
• Posts: 37
• Joined: 08-March 11

## Re: Big Oh Notation Algorithm

Posted 20 November 2011 - 06:11 PM

mostyfriedman, on 20 November 2011 - 05:29 PM, said:

think .. if n is 100, do you think A will be faster or B, and why?

B will be faster until we make n greater than 10001. Once we make n greater than 10001 A will be faster.

Am I understanding this correctly?

### #6 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: Big Oh Notation Algorithm

Posted 20 November 2011 - 06:31 PM

yes