Как найти сложность времени и большой O?

Question

Для следующего фрагмента кода предоставьте построчный анализ и создайте функцию T (n), которая дает время выполнения этого фрагмента кода как функцию «n». Также определите значение O для этого фрагмента кода.

x = 10,000;
for (int i = 1; i <= n; i++) {
if ( x < i)
sum += foo( i );``
system.out.print(sum);
else
for (j = 1; j <= i; j++)
system.out.print( i );
system.out.println( );
}
foo (a) {
for (int i = 0; i < n; i++)
sum += a * i;
return sum;
}

Answer 1

x = 10,000; 

1: занимает 1 фиксированный произвольный интервал общего времени, делая это O (1)

for (int i = 1; i <= n; i++) {

2: выполняется n раз, поэтому время теперь O (n), поскольку O (n)> > O (1) [где >> означает намного больше, чем]

if ( x < i)
sum += foo( i );``
system.out.print(sum);

3: эти строки выполняются в O (n) благодаря for для l oop в foo, так как это вложено, время здесь равно O (n ^ 2) для n> 10000

else
for (j = 1; j <= i; j++)
system.out.print( i );
system.out.println( );
}

4: Это также будет работать n раз в пределах l oop, поэтому O (n ^ 2) для времени <10000 </p>

foo (a) {
for (int i = 0; i < n; i++)
sum += a * i;
return sum;
}

5: см. 3-й комментарий

Окончательный вариант: поскольку это выполняется в O (n ^ 2) для n> 10000 и n <10000, эта функция равна O (n ^ 2) </p>