5 Replies - 825 Views - Last Post: 20 November 2011 - 06:31 PM Rate Topic: -----

#1 volvera215  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 volvera215  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#4 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#5 volvera215  Icon User is offline

  • New D.I.C Head

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

Re: Big Oh Notation Algorithm

Posted 20 November 2011 - 06:11 PM

View Postmostyfriedman, 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?
Was This Post Helpful? 0
  • +
  • -

#6 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Big Oh Notation Algorithm

Posted 20 November 2011 - 06:31 PM

yes
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1