For the following parts, try to get the best Big-O estimate that you can and briefly justify your answers.
Part a)
int i, j;
int n = 100;
for (i = 1; i <= n; i++) {
for (j = 3*i; j <= n; j++) {
printf("programming is fun\n");
}
}
Part b)
int i, j;
int n = 1000000;
for (i = 1; i <= n; i++) {
for (j = 1; j <= 10000; j++) {
printf("%d %d\n", i, j);
}
}
Part c)
int i = 0;
int n = 10;
int j;
while (i < n) {
i++;
j = i;
while (i < n) {
printf("hello %d\n", i);
i++;
}
i = j;
}
Part d)
int i = 0;
int n = 10;
int j;
Page 5 of 6
while (i < n) {
i++;
j = i;
while (i < n) {
printf("hello %d\n", i);
i++;
break;
}
i = j;
}
Part a)
int i, j;
int n = 100;
for (i = 1; i <= n; i++) {
for (j = 3*i; j <= n; j++) {
printf("programming is fun\n");
}
}
================================================================
Answer: O(n2)
Explanation: As we can see there are two for loop one
nested on another. Lets say if n = 3, the program will run for 3*3
=> 9 times. So the idea if the upper for loop will run for n
time and then inner runs each n times for every iteration of upper
for loop
n + n + n + n + n .. ..n times => n*n
=================================================================
Part b)
int i, j;
int n = 1000000;
for (i = 1; i <= n; i++) {
for (j = 1; j <= 10000; j++) {
printf("%d %d\n", i, j);
}
}
================================================================
Answer: O(n2)
Explanation: As we can see there are two for loop one
nested on another. Lets say if n = 3, the program will run for 3*3
=> 9 times. So the idea if the upper for loop will run for n
time and then inner runs each n times for every iteration of upper
for loop
n + n + n + n + n .. ..n times => n*n
If ith n = 1000000 and for jth we have 1000 , Then TOTAL
TIMES = 1000000 * 1000 = 109
=================================================================
Part c)
int i = 0;
int n = 10;
int j;
while (i < n) {
i++;
j = i;
while (i < n) {
printf("hello %d\n", i);
i++;
}
i = j;
}
================================================================
Answer: O(n2)
Explanation: As we can see there are two while loop one
nested on another. Lets say if n = 3, the program will run for 3*3
=> 9 times. So the idea if the upper while loop will run for n
time and then inner runs each n times for every iteration of upper
for loop
n + n + n + n + n .. ..n times => n*n
=================================================================
Part d)
int i = 0;
int n = 10;
int j;
Page 5 of 6
while (i < n) {
i++;
j = i;
while (i < n) {
printf("hello %d\n", i);
i++;
break;
}
i = j;
}
================================================================
Answer: O(n)
Explanation: As we can see there are two for loop one
nested on another.So the idea if the upper while loop will run for
n time and then inner runs once once as there is break
statement
1 + 1 + 1 + 1 + 1 + ...n times = n
=================================================================
For the following parts, try to get the best Big-O estimate that you can and briefly...
For each of the below code snippets, identify the bounding function (the big O) of the number of times the indicated line is run (justify your answer briefly): int i = 1: while (i < n) { printf ("Insert difficult work here!") i = i + i: } for(i = 0: i < n: i++) { for (j = 0: j < n: j++) { for (k = 0: k < n: k++) { if(i==j && j==k) arr[i] [j] [k]...
(10') 6. For each of the following code blocks, write the best (tightest) big-o time complexity i) for (int i = 0; ǐ < n/2; i++) for (int j -0: ni j++) count++ i) for (int í = 0; i < n; i++) for (int ni j0 - for (int k j k ni kt+) count++ İİİ) for (int í ー 0; i < n; i++) for(int j = n; j > 0; j--) for (int k = 0; k...
Which big-O expression best characterizes the worst case time complexity of the following code? public static int foo(int N) ( int count = 0; int i1; while (i <N) C for (int j = 1; j < N; j=j+2) { count++ i=i+2; return count; A. O(log log N) B. O(log N2) C. O(N log N) D. O(N2)
Using C++ please explain What is the Big-O time complexity of the following code: for (int i=0; i<N; i+=2) { ... constant time operations... Select one: o a. O(n^2) O b. O(log n) c. O(n) O d. 0(1) What is the Big-O time complexity of the following code: for(int i=1; i<N; i*=2) { ... constant time operations... Select one: O O a. O(n^2) b. 0(1) c. O(n) d. O(log n) O What is the Big-O time complexity of the following...
1. Determine the appropriate big-o expression for each of the following functions, and put your answer in the table we have provided in section 2-1 of ps5_parti. We've included the answer for the first function. (Note: We're using the “ symbol to represent exponentiation.) a (n) = 5n + 1 b. b(n) = 5 - 10n - n^2 o c(n) = 4n + 2log (n) d. e. d(n) = 6nlog (n) + n^2 e(n) = 2n^2 + 3n^3 - 7n...
Determine the Big 0 provide the order (Big O) of the execution speed also determine the exact execution speed. public class CountIt { public long SnippetNestedLoop(long n) { long i, j, x = 0; i=0; x++; while(i<n){ x++; //i<n // SomeStatement // j = 0; // j < n // SomeStatement // j++; // Can you explain why is this here? // i++; // Can you explain why is this here? Ans: i < n } } } x++; return...
**how can I make my program break if 0 is entered by user as last number not always 10 numbers output should be enter 10 numbers:1 2 0 numbers entered by user are: 1 2 Largest number: 2 **arrays can ONLY be used in the main function, other than the main function pointers should be used #include #define N 10 void max(int a[], int n, int *max); int main (void) { int a [N], i , big; printf("enter %d numbers:",N);...
10 What does the last printf in this code print to the screen? a)n-7 b)n- 0 c)n--1 d) None of the above 鬐include< stdio. h> int main) int n-0 for (n-7: n<O; n-- printf (n") printf ("n *%d", n); - return 11-What does the code print to the screen? 鬐include< stdio.h> void fun (int) int main) b) 8 d) None of the above fun (3) return void fun (int a) int x-10 while(a !_ 3 x > s} if a...
Find Big-O notation for the following algorithm: int function9(int n) { int ij for (i-0; in; i++) for (0; j<n; j++ if (j1) break return j; } int function9(int n) { int ij for (i-0; in; i++) for (0; j
1. Give the big-O characterization of the following loops, in terms of parameter n, and justify your answer: a) for (int i=1; i<=n, i++) {for (int j=1; j<=n; j++) {a constant-time operation}} b) for (int i=1;i<=n, i++) {for (int i=1; j<=i; j++) {a constant-time operation}} c) for (int i=1;i<=n*n, i++) {for (int j=1; j<=n; j++) {a constant-time operation }} d) for (int i=1; i<=n*n, i++) {for (int j=1; j<=i; j++) {a constant-time operation }} e) for (int i=1; i<=n, i++)...