java - Big-O of These Nested Loops -

java - Big-O of These Nested Loops -

i'm pretty new big-o field, bear me here. have been searching much still need lot of work understand it. came across these nested loops in practicing exercises , there wasn't solutions , seem complicated. so, help appreciated.

1) int sum=0; for(int i=0; < n^2; i++) { // n+1 for(int j = n-1; j >= n-1-i; j–-) { // n(n+1)/2 ? sum = i+j; // n(n+1)/2 ? system.out.println(sum); // n(n+1)/2 ? } }

big-o = ?

2) int sum=0; for(int i=1; <= 2^n; i=i*2) { // log(n) for(int j=0; j <= log(i); j++) { // log(n(n+1)/2) ? sum = i+j; // log(n(n+1)/2) ? system.out.println(sum); // log(n(n+1)/2) ? } }

big-o = ?

3) int sum = 0; int k = 23; for(int i=k; <= 2^(n−k); i=i*2) { // log(n) for(int j=2^(i−k); j < 2^(i+k); j=j*2) { // log(log(n)) ? sum = i+j; // log(log(n)) ? system.out.println(sum); // log(log(n)) ? } }

big-o = ?

4) int sum=0; for(int i=2n; i>=1; i=i/2) { for(int j=i; j>=1; j=j/2) { sum = i+j; system.out.println(sum); } }

big-o = ?

edit: - corrected #4. sorry mess up. - base of operations of log 2. - ^ here means "to power", not xor.

there plenty questions "big-o of nested loops" here on stackoverflow (and answers).

however, reply me. first there notation problem: tagged question java. in code see 2ⁿ or n². in java means xor, think meant math.pow(2,n) instead, reply treat powerfulness operator.

int sum=0; for(int i=0; < n^2; i++) { // outer loop for(int j = n-1; j >= n-1-i; j–-) { // inner loop sum = i+j; // inner operations system.out.println(sum); } }

the inner operations runs in o(1), counting how called.

the outer loop runs n² times. for each i (from outer loop) inner loop runs i times.

in total 0+1+...+(n²-1)+n² = n²(n²+1)/2. in Θ(n⁴).

int sum=0; for(int i=1; <= 2^n; i=i*2) { // outer loop for(int j=0; j <= log(i); j++) { // inner loop sum = i+j; // inner operations system.out.println(sum); } } the outer loop runs n times, since 2⋅2⋅2⋅...⋅2 (n times) equals 2n. the inner loop runs k times each i=2k (1 ≤ k ≤ n), assuming base of operations of logarithm 2.

in total 1+2+3+...+n-1+n = n(n+1)/2. in Θ(n²).

int sum = 0; int k = 23; for(int i=k; <= 2^(n−k); i=i*2) { // outer loop for(int j=2^(i−k); j < 2^(i+k); j=j*2) { // inner loop sum = i+j; // inner operations system.out.println(sum); } } the outer loop runs m times m minimal such k⋅2m > 2n-k holds. can written k⋅2k⋅2m > 2n. k has positiv (otherwise outer loop run forever). assuming k bounded o(n) (canstants in o(n)), m bounded o(n). the inner loop runs 2⋅k times, no matter i or n is. in o(1) constant k , in o(n) k bounded o(n).

in total o(n) constant k , o(n²) k in o(n).

int sum=0; for(int i=2n; i>=1; i=i/2) { // outer loop for(int j=i; j>=1; j=j/2) { // inner loop sum = i+j; // inner operations system.out.println(sum); } } the outer loop runs log(n) times in case 2 (the other way around) the inner loop runs j times (basicly) each powerfulness of 2 between 1 , 2n.

assuming n = 2k (means log(n) = k) in total 2k+1+2k+2k-1+...+22+21+20=2k+2-1=4n-1. in in o(n). holds n not powerfulness of 2.

java performance loops big-o time-complexity