This code is to find sum of even numbers in Fibonacci sequence. I just wants to know the Time complexity of this program
int sum = 2;
int a = 1;
int b = 2;
while (a < 4000000) {
int c = a;
a = b;
b = c + b;
if (b % 2 == 0) {
sum += b;
}
}
System.out.println(sum);
I would be thankful if I get an explanation too.
First, this specific code snippet has constant time complexity as it does not have any variable defining the time of execution.
Let's assume that the limit 4000000 defines such variable parameter thus limiting maximum Fibonacci number Fk < N:
public static int sumEvenFibos(int n) {
int sum = 2;
int a = 1;
int b = 2;
int k = 1; // index of Fibonacci number
while (a < n) {
int c = a;
a = b;
b = c + b;
if (b % 2 == 0) {
sum += b;
}
k++;
}
System.out.println("sum=" + sum + "; k=" + k + " for n=" + n);
return sum;
}
Then this function has lower time complexity than O(N) because the k-th Fibonacci number a grows non-linearly according to Binet's formula which can be expressed asymptotically as: Fk ~= φ^K / sqrt(5), where φ = (1 + sqrt(5))/2 > 1 is golden ratio.
Thus, in the the loop at most k Fibonacci numbers are calculated, that is:
Fk < N, φ^K / sqrt(5) < N --> φ^K < N * sqrt(5)
hence,
K < log(N * sqrt(5)) / log (φ)
As the constant values can be ignored when defining time complexity, T(N) = O (log N).
The number of sum operations for even Fibonacci numbers is K/3 because each third Fibonacci number is even:
1 1 2 3 5 8 11 13 24 etc.
Test & Output
int[] ns = {
10, 100, 1000, 10_000, 100_000,
1000_000, 2000_000, 4000_000,
10_000_000, 20_000_000, 40_000_000,
80_000_000, 160_000_000
};
Arrays.stream(ns).forEach(MyClass::sumEvenFibos);
---------
sum=10; k=6 for n=10
sum=188; k=11 for n=100
sum=3382; k=16 for n=1000
sum=14328; k=20 for n=10000
sum=257114; k=25 for n=100000
sum=1089154; k=30 for n=1000000
sum=4613732; k=31 for n=2000000
sum=4613732; k=33 for n=4000000
sum=19544084; k=35 for n=10000000
sum=19544084; k=36 for n=20000000
sum=82790070; k=38 for n=40000000
sum=82790070; k=39 for n=80000000
sum=350704366; k=40 for n=160000000
This is simple. You iterate over all elements in the collection - this is O(n) or linear complexity
The Time complexity of this program will be (n+5)+3+1 = n+9 = o(n) and below is the calculation....
`int sum = 2; // constant =1
int a = 1; //constant = 1
int b = 2; //constant = 1
while (a < 4000000) { //loop = n
int c = a; //constant = 1
a = b; //assigning value = 1
b = c + b; //assigning value = 1
if (b % 2 == 0) { //if condition = 1
sum += b; // addition = 1
}
}
System.out.println(sum); // output = 1
so the time complexity will be o(n) and short trick of finding time complexity is check loops inside code so if one loop so complexity is n and if nested loop complexity is n^2 and if two loop up and below so complexity is 2n and same for all other. Thanks.
