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