Вычисление временной сложности метода вызова в вызове метода

Question

http://imgur.com/a/efinr

Так что я была поставлена ​​задача создания методов в Java, которые делают основные операции (сложение, вычитание, умножения) с HugeIntegers (которые являются массивами, дом цифры в их индексах, например, 1111 будет [1,1,1,1]).

После написания нашего кода нас попросят проанализировать его временную сложность (например, классы сложности большой тета), и у меня возникает небольшая проблема с анализом части моего кода (см. Ссылку).

Я знаю, что x1.add (diff) даст мне большую тету (n), где n - количество цифр HugeInteger, а compareTo (x2) также даст мне большую тета (n). Содержимое внутри цикла while также является большой тета (n). Теперь, суммарная временная сложность этого куска кода большой тета (n^3) или будет n^2? У меня возникают проблемы с условием цикла while, поскольку я не уверен, что n следует добавлять или умножать. Я знаю, что любой этот результат будет умножен на n внутри цикла while.

Любая помощь очень, очень ценится. Я занимаюсь этим в течение большей части недели.

Answer 1

Условие цикла будет выполняться по одному на каждую итерацию цикла. Содержимое цикла также будет запускаться один раз для каждой итерации цикла. Поэтому вы можете добавить их. Затем, разумеется, умножьте количество циклов цикла. Если условие (n) и тело цикла (n), то вместе они все еще (n). Если цикл работает (n) раз, то сумма равна (n^2).