# Determining runtime of a theoretical program (question of extraordinary complexity)?

I apologize in advance, as I don't have a clue to which stackexchange to post this question! I beg you to not delete this question, as I have chronic pain and it is very important to me!!! I actually written this hours, a lot of effort went into this question...

### How does one determine runtime of a theoretical program???

• This is a theoretical question about a program I want to make. I might just ask now to save myself a lot of time!
• Is the following program even calculable on PC in general (my specs: Intel i5 9600KF, Geforce 3070) in reasonable time-frame??? As it is possible it would take years!
• It doesn't have to be an exact specification, but it can be an estimate! I Am more interested if it is even possible (right now)

# Description of a Program:

It is a diet program, which purpose is to give you foods in grams to eat to achieve dietary goals...

# Number of permutations:

Lets say: you have 10 nutrients in a tomato, that's 10 floating point numbers. Multiply this by 100, because you can select 1-100g of a food. And lets say you are choosing from a pool of 30 foods. That's (10*100)^30 of permutations program would have to consider, not even mentioning doing actual calculations in practice!

# What I want to achieve:

Now this is quite complicated and I have low verbal intelligence so listen closely!!! I want to make a program which basic function would be: compare all permutations of substances included in foods with each other to give you amounts of foods to eat: so all your nutrient intakes (e.g. Vitamin D) would get closest to their respective RDA goals!

Note: field of science "nutrigenetics" allows you to get estimates for your personal RDA goals!

A program would have to take into an account all portions between 1-100gram of foods. E.g. it would enumerate amounts of nutrients contained per 1-100g of a tomato, so you would end up with a list of amounts of all nutrients per 1g, 2g, 3g... until 100g. And it would do this for all other foods in a database as well!

So you would end up with a list of all substances contained per 1-100g of a range of foods.
Like: contents of Vitamin A,B,C,D... per (1-100g) of a tomato, citrus, apple and so on... These numbers are usually in unit mg and they include mostly floating-point numbers e.g. 1.245mg of Vitamin C, 20.5mg of sugar, 4.6765mg of Vitamin D... anyways you get the picture.

So you would end up with a list (lets say you added 30 foods to your database) of 30 foods, which have all of their nutrients listed under them, i.e. for their respective portions (1-100g). And then the program would try to find the best permutation (between picking 1-100g amounts of all selected foods) so you reach your RDA goals...

To further illustrate this:
(You enter into your database nutrient contents of a food per 100g) e.g. in practice this would mean - food 1: tomato, portion selected: 1g, calculate contents of vitamin (A,B,C,D...) = 20.12, 10.542, 5.1123, 7.37... Then it would calculate amounts of nutrients for portion selected: 2g and so on...

Same process with a food 2: orange, portion selected: 1g, calculate contents of vitamin (A,B,C,D...) = 13.56, 23.5854, 10,332, 7,332...

# Theoretical framework of the program:

Note: I do not have actual understanding how this program would proceed programmatically in calculating this yet, so in theory only!

This program would have to add together large amounts of numbers of all substances from different foods. And then evaluate, if yields (of all substances of all foods added together) for selected amounts of foods are matching all your RDA goals!

But for example: (let's say you have 5 foods for simplicity) tomato, apple, orange, pear, kiwi. Let's say all have contents of Vitamin A. That would be 5 numbers to add together like: 1.23232 + 4.65 + 15.67 + 31.17 + 4.112 (this example omits 1-100g portions of all foods selected and all other nutrients contained within these foods). Then program would have to check if nutrients contained in amounts of foods (it selected) match all your RDA goals: e.g. 40mg of sugar, 10 000mg of Vitamin A, 500mg of Vitamin D, 400 mg of magnesium, 1000 mg of calcium.

Aside: we could also allow 10% deviation from RDA goals and if not met: it would start calculations over.

I guess because sheer amounts of calculations, for sake of performance: it would compare old results, to new permutations (once calculated) probably in bursts for sake of performance. Rather than calculating all permutations once and then picking the best one!

## Note:

- I use word substances and nutrients interchangeably!
- I refer to a portion as selecting a part between 1-100g of a food e.g. tomato.
- I Am not even sure, if I Am using word enumerate right in this context, I use it as taking all items from a list and assigning them some number like: giving variable "25mg of tomato" - value named "Vitamin C" = 1.13232. So in the end all foods have assigned all of their substances to them for their respective portions 1-100g!!!

• Just for you to know (without any connection to the actual question in hand), even if the question is deleted, it is actually just being hidden. The post owner and moderators still have access to the post itself - so don't worry! Jan 12, 2022 at 0:39
• Jan 12, 2022 at 6:20

This is feasible to compute in fairly fast (polynomial) time with linear programming.

This problem seems like a poster problem for linear programming where you specify a set of equalities and inequalities, e.g. tomato between 0 and 100 grams, apple between 0 and 100 grams and then if each gram of a tomato has 1 mg of vitamin X and each gram of an apple has 2 mg of vitamin X and you aim for 7 mg of vitamin X you specify $$1 * tomato + 2 * apple = 7$$.

In practice there may be no exactly correct solution so you will have to instead make some of the equalities into a function that will be optimized to match as closely to your goals as possible.

The program does not have to iterate over each gram of each food, it takes the inequalities and computes the correct weights of our foods.

• That is most interesting! Is this kind of programming possible in C++ ? Thanks! Jan 11, 2022 at 23:19
• Yes, it is possible in any (Turing complete) programming language. Jan 11, 2022 at 23:22
• I have to buy a new computer and need to make some considerations which hardware to buy! Is it possible to run program like that on GPU for better performance? I have RTX 3070, I wonder whether or not I need better CPU. I think even Intel Core i3-12100F is fine for most programming in C++ I Am not sure if this can be run on GPU tho, not sure if it is possible to tell ahead even! Otherwise I might need to consider buying better CPU, so later I don't find out it is not powerful enough - that would be annoying! Thanks! Jan 17, 2023 at 10:33

I just copied my answer from a similar question: Since you are asking in Computer Science, I very much recommend George Dantzig's "Linear Programming and Extensions". It explains linear programming in a way that a normal human being (like me) can understand. The link has links to three .pdf files of this book.

https://www.rand.org/pubs/reports/R366.html

This was invented in 1952, I think, and was used for practical problems using mechanical calculators. No computers involved. For five items and ten ingredients this is quite a trivial problem actually, that should be solved in less than a millisecond.