# Is it possible to estimate used gas based on algorithm's Big O?

[Example Algorithm 1]: I have an array of structs(`PaymentReceipt[] paymentReceiptList;`) and imagine there are around 1000 pushed items and array's size keep increases. Each item has a time_start and time_end value. Inside my contract's function, I have to iterate all those members to check if any two intervals overlap among a given set of intervals, which is O(n) time.

[Example Algorithm 2]: I use an algorithm function to compute nth Fibonacci number to find 1000th value. This is a recursive function to compute nth Fibonacci number and is of O(log(n)) time.

For Algorithm_1, with a small set, and for Algorithm_2 if nth value is small there should be no problem. But large size of the array on Algorithm_1 and large value for n on Algorithm_2, I may face with inefficient gas problem. I was not sure will both of those algorithms will consume high amount of gas or not based on given `n`. I want to figure out the highest `n` that I can use for both algorithms based on given gas amount.

[Q] Is it adviced to do O(n) and O(log(n)) time algorithms inside a Contract's function, if yes, is there any way to estimate the required gas as some kind of function based on the given `n` for the each algorithm?

=> Related to previous question; does used gas changes for each algorithm as same ratio with O() time?

For example: For Algorithm_1: Can we say that does the used gas will have same ratio with O(n) time.

``````O((n=10))       usedGas=10
O((n=100))      usedGas=100
O((n=1000))     usedGas=1000
``````

For Algorithm_2: or can we say that does the used gas will have same ratio with O(log(n)) time.

``````O(log(n=10))    usedGas=10
O(log(n=100))   usedGas=20
O(log(n=1000))  usedGas=30
``````

Thank you for your valuable time and help.

Algo 2: The calculation you linked looks O(n) to me because of the `for (int i=2;i<n;i++)` loop. On the other hand, it looks like people have O(1) calculations for Fibonacci: https://stackoverflow.com/questions/6037472/can-a-fibonacci-function-be-written-to-execute-in-o1-time
Gas calculations will also depend on whether you have `if then else` inside the loop. These branching statements will influence the gas cost of each execution of the loop. So I see no beautiful calculation of gas before you actually try it...
• Thank you. Algorithm_2 was some kind of example for a recursive call sorry I didn't mention in the question., maybe instead of Fibonacci, imagine that I do some recursive call and each iteration there will be multiple `if then else`. Should I check remaining gas on the run time of the code? What do you mean by intermediate state? @Xavier Leprêtre B9lab. PS: I updated link for Algoritm_2 with O(log(n)) – alper Jan 26 '17 at 16:30