Fibonacci algorithm complexity. I have written a program that shows fibonacci numbers in a given range.

Question

I would like to determine its complexity and I want to know if it is more efficient than recursive fibonacci algorithm

swift code

func fibonacci (a:Int) {
var holder1: Int = 1
var holder 2: Int = 1
for i in 1...a {
if i%2 ==0 {
print(holder2)
holder2 = holder1 + holder2
}
else {
print(holder1)
holder1 = holder2 + holder 1
}
}
}

Answer 1

The recursive fibonacci works in ~O(1.6^n) time. It is very very very slow. Yours (dynamic) solution works in O(n) time (linear time) which is much better. The best possible way is in ~O(log(n)) time which is much better than linear time (it is possible using matrix multiplication).

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Answer 2

Jhon
No. Just look, while you are doing each iteration of for statement, then you do 'if' or 'else'. Then it is one operation each time. Then one operation * n times gives you O(n) time.

Answer 3

how did you calculate that mine is O(n) time? wouldn't it be quadratic time??

Answer 4

Thank you. I got it