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 15 Replies  995 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
