Need help with calculating big-O notation. I tried but still confused. Please explain your answers like below. public st
Posted: Wed Apr 27, 2022 3:06 pm
Need help with calculating big-O notation. I tried but still
confused. Please explain your answers like below.
public static void a(int n) { // O(3n+2) = O(n)
int a = 0; // 1
int i = 0; // 1
while (i < n) { // n
a = i; //
n
i++; //
n
}
}
public static void b(int n) { // O(n+2) =
O(n)
int a = 0; // 1
for(int i = 0; i < n; i +=
3) { // 1 + n/3 + n/3
a = i; //
n/3
}
}
public static void c(int n) { //
O(n^2)
int a = 0; // 1
int i = 0; // 1
while (i < n) { // n
for (int j
= n; n > 0; n = n/10) { //
a = i + j;
}
i++; // n
}
}
public static void d(int n) { O(3n^2+4n+2) =
O(n^2)
int a = 0; // 1
for(int i = 0; i < n; i +=
1) { // 1 + n + n
for(int j
= i; j < n; j += 1) { // (n + n + n)n
a = i + j; // 2n
}
}
}
public static void e(int n) { O(4n^2 + 4n + 2) =
O(n^2)
int a = 0; // 1
for(int i = 0; i < n * n;
i += 1) { // 1 + n^2+ n^2
for(int j
= 0; j <= n; j += 1) { // (1 + n + 1 + n) n
a = i + j; // n
}
}
}
public static void f(int n) { O(nlog(n))
int k = 1, a = 0; // 1 +
1
for(int i = 0; i < n; i +=
1) { // 1 + n + n
for(int j
= 0; j <= k * 2; j += 1) { n(1+
a = i + j;
}
k = k *
2;
}
}
confused. Please explain your answers like below.
public static void a(int n) { // O(3n+2) = O(n)
int a = 0; // 1
int i = 0; // 1
while (i < n) { // n
a = i; //
n
i++; //
n
}
}
public static void b(int n) { // O(n+2) =
O(n)
int a = 0; // 1
for(int i = 0; i < n; i +=
3) { // 1 + n/3 + n/3
a = i; //
n/3
}
}
public static void c(int n) { //
O(n^2)
int a = 0; // 1
int i = 0; // 1
while (i < n) { // n
for (int j
= n; n > 0; n = n/10) { //
a = i + j;
}
i++; // n
}
}
public static void d(int n) { O(3n^2+4n+2) =
O(n^2)
int a = 0; // 1
for(int i = 0; i < n; i +=
1) { // 1 + n + n
for(int j
= i; j < n; j += 1) { // (n + n + n)n
a = i + j; // 2n
}
}
}
public static void e(int n) { O(4n^2 + 4n + 2) =
O(n^2)
int a = 0; // 1
for(int i = 0; i < n * n;
i += 1) { // 1 + n^2+ n^2
for(int j
= 0; j <= n; j += 1) { // (1 + n + 1 + n) n
a = i + j; // n
}
}
}
public static void f(int n) { O(nlog(n))
int k = 1, a = 0; // 1 +
1
for(int i = 0; i < n; i +=
1) { // 1 + n + n
for(int j
= 0; j <= k * 2; j += 1) { n(1+
a = i + j;
}
k = k *
2;
}
}