9 replies to this topic

[recon]

Implement in c the monte carlo algorithm and find the time complexity

[WingedPanther]

Do you have any code yet?

[recon]

No I need Help in that one

[WingedPanther]

We don't do homework for you. What part are you having trouble with? There are a LOT of pieces involved, and you've given no indication where your issue is.

[recon]

you can find area under the curve f(x)= e^x cosx and then find time complexity. Or some other problems related numerical methods.
I can do programming but unable to get referance about Monte Carlo algo. If you give me small example and illustrate the time complexity then i will able to develop so

[WingedPanther]

http://en.wikipedia....te_Carlo_method

It's not a single algorithm, it's an approach to solving a category of problems. Which particular problem you are solving will determine the details.

[recon]

My Problem is

Quote

Write a C program to implement Monte Carlo algorithm to find area under the curve y= e^-x

between the limits a=0 and b=1. Determinte how many cycles are required to obtain an answer

that is accurate to three significant figures. Compare the Computer time required for this

problem with the time required for problem ( find area under the curve y= e^-x using

trapezoidal Rule ) . Discuss the Time Complexity in this Monte Carlo method.

// Program for trapezoidal Rule  is as follows

#include<stdio.h>
#include<conio.h>
#include<math.h>

double fun1(double x)
{ return((double)exp(-x));
  }

void main()
{ double y[30],a,b,h,ans1,z=0.0;
  int i,n;
  clrscr();
  printf("\n Enter Upper limit : ");
  scanf("%lf",&b);
  printf("\n Enter Lower limit : ");
  scanf("%lf",&a);
  printf("\n How many Intervals : ");
  scanf("%d",&n);

  h=(double)(b-a)/n;

  for(i=0;i<=n;i++)
  { y[i]=fun1(a+i*h);
    printf("\nY[%d] : %lf",i,y[i]);
   }
  for(i=1;i<n;i++)
   z+=y[i];

  ans1=(h/2)*((y[0]+y[n])+2*z);
  
  printf("\n\n Observed Solution is : %lf ",ans1);
  
getch();
}

Edited by Alexander, 20 October 2010 - 06:39 PM.
Please add [code] tags around your code

[WingedPanther]

Monte Carlo Integration

[recon]

but i have main problem in Time complexity. I had been tried to learn thoritically but not able to find time complexity of monte carlo problem.

Any One please give some idea about time complexity finding technique..........................................

[WingedPanther]

If you've written the code, then you can analyze it for time complexity. Different implementations of the same algorithm can have different complexities.