2

[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.

2

Algo 1: you should implement it so that when an interval is added, it is immediately checked for overlap with the existing ones. You then save the outcome of this check in storage. Not easy because that would mean keeping 1 or 2 ordered lists. This might become O(log n) and so should be possible without blowing up gas.

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

You should not do any O(n) calculations, or, if you do, then spread them across multiple transactions. The way to do that, is to check for remaining gas, and save the intermediate state if it gets low.

O(log n)is fine.

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
  • 1
    If you do a long-winded operation that spans multiple transactions, then yes, you need to check remaining gas at run time. Intermediate state: if you want to do var i 0 to 1000, you may only be able to do 0 to 500 in first transaction and 501 to 1000 in the next. You need to save this 500 in the storage to pick up later. 500 is the "intermediate state". – Xavier Leprêtre B9lab Jan 26 '17 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.