Running time of Computing Fibonacci series using Formula

Reply to Thread

Discussion in 'Homework Help' started by zulfi100, Feb 11, 2016.

Reply to Thread

Feb 11, 2016 #1

zulfi100 Thread Starter Active Member

Jun 7, 2012

395

1

Hi,
Book has provided a formula for computing Fibonacci series which was discovered by A. de Moivre. The formula is given below:

Fib(n) = Φ raised to the power n/ square root of 5

Can some body please guide me what’s its running time?

Zulfi.

#1 Like Reply
Feb 11, 2016 #2

WBahn Moderator

Mar 31, 2012

20,254

5,759

That depends on how long it takes to raise a constant to an integer power, and that depends on the algorithm used to calculate the value of a constant raised to an integer power, doesn't it?

#2 Like Reply
Feb 11, 2016 #3

zulfi100 Thread Starter Active Member

Jun 7, 2012

395

1

Hi,
I found that the run time of power function is log(n).
http://stackoverflow.com/questions/5231096/time-complexity-of-power.

Thats the advantage of his technique otherwise the iterative version takes O(n) time.

Zulfi.

#3 Like Reply

Loading...

Related Forum Posts:

Fibonacci Number Checker Using Logisim

Posted by LimOn Khan in forum: The Projects Forum

Replies:

1

Views:

519
Running Time of Insertion Sort

Posted by zulfi100 in forum: Homework Help

Replies:

0

Views:

170
Running Time of Selection Sort

Posted by zulfi100 in forum: Homework Help

Replies:

1

Views:

186
Fibonacci Series Generator

Posted by Hasnatsaeed in forum: The Projects Forum

Replies:

17

Views:

6,566
universal time constant formula

Posted by ra1ph in forum: Homework Help

Replies:

8

Views:

3,180
The Future of Computing

Posted by Mike M. in forum: Off-Topic

Replies:

18

Views:

4,299

You May Also Like: