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.

# Big Oh Notation Algorithm

Page 1 of 1## 5 Replies - 1497 Views - Last Post: 20 November 2011 - 06:31 PM

##
**Replies To:** Big Oh Notation Algorithm

### #2

## 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

## 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?

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

### #4

## 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

## Re: Big Oh Notation Algorithm

Posted 20 November 2011 - 06:11 PM

Page 1 of 1