1 Replies - 274 Views - Last Post: 08 February 2013 - 10:52 AM Rate Topic: -----

#1 ishan3243  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 17
  • Joined: 29-October 12

uniform cost v/s logarithmic cost

Posted 08 February 2013 - 09:37 AM

can anyone explain me the time complexity of factorial function if we follow RAM model and if we follow logarithmic cost concept.

int fact(int N) {
j=1; prod=1;
while (j<=N) {
j=j+1; prod=prod*j;
}
return prod;
}


Is This A Good Question/Topic? 0
  • +

Replies To: uniform cost v/s logarithmic cost

#2 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: uniform cost v/s logarithmic cost

Posted 08 February 2013 - 10:52 AM

The logarithmic cost concept means each operation has a cost that is proportional to the size of the input. 0 + 1 will cost 1 because all operations will execute over 1 bit, but 100000 + 1 will cost 6 because the operation will have to loop across 6 bits. You will have to figure out how the size of j and prod scale accross all iterations to find the runtime.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1