How do I calculate the polynomial f(x) for big-o notation? [closed]
Hi I am a student in a Java course and we just covered Big-O notation.
I understand the general picture of Big-O, where it takes the worst-case scenario, and then it calculates the efficiency of the code, and I understand the general run-times of each process. I can say that the run-time of the code below is O(n^2).
What I am having trouble with is calculating the polynomials. Right now, I just look at a code snippet and know the efficiency, but I do not know the snippet's f(x) or its reference function (g(x)).
Could I get help with finding the f(x) and g(x) for the following code? (only the process for finding the answer is necessary, exact answers not needed)
Links to documents or videos that deal with this topic would also be helpful. Thanks!
public static int num_occurrences(int n)
int count = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if ( i == j )
continue;
if (strings[i] == strings[j])
count++;
return count;
java big-o polynomials
edited Nov 12 '18 at 4:26
suvojit_007
1,3251517
asked Nov 12 '18 at 3:43
JarackJarack
34
closed as off-topic by Stephen C, gnat, EdChum, Unheilig, V-rund Puro-hit Nov 12 '18 at 9:58
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – Stephen C, EdChum, V-rund Puro-hit
add a comment |
Hi I am a student in a Java course and we just covered Big-O notation.
I understand the general picture of Big-O, where it takes the worst-case scenario, and then it calculates the efficiency of the code, and I understand the general run-times of each process. I can say that the run-time of the code below is O(n^2).
What I am having trouble with is calculating the polynomials. Right now, I just look at a code snippet and know the efficiency, but I do not know the snippet's f(x) or its reference function (g(x)).
Could I get help with finding the f(x) and g(x) for the following code? (only the process for finding the answer is necessary, exact answers not needed)
Links to documents or videos that deal with this topic would also be helpful. Thanks!
public static int num_occurrences(int n)
int count = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if ( i == j )
continue;
if (strings[i] == strings[j])
count++;
return count;
java big-o polynomials
edited Nov 12 '18 at 4:26
suvojit_007
1,3251517
asked Nov 12 '18 at 3:43
JarackJarack
34
closed as off-topic by Stephen C, gnat, EdChum, Unheilig, V-rund Puro-hit Nov 12 '18 at 9:58
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – Stephen C, EdChum, V-rund Puro-hit
add a comment |
Hi I am a student in a Java course and we just covered Big-O notation.
I understand the general picture of Big-O, where it takes the worst-case scenario, and then it calculates the efficiency of the code, and I understand the general run-times of each process. I can say that the run-time of the code below is O(n^2).
What I am having trouble with is calculating the polynomials. Right now, I just look at a code snippet and know the efficiency, but I do not know the snippet's f(x) or its reference function (g(x)).
Could I get help with finding the f(x) and g(x) for the following code? (only the process for finding the answer is necessary, exact answers not needed)
Links to documents or videos that deal with this topic would also be helpful. Thanks!
public static int num_occurrences(int n)
int count = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if ( i == j )
continue;
if (strings[i] == strings[j])
count++;
return count;
java big-o polynomials
edited Nov 12 '18 at 4:26
suvojit_007
1,3251517
asked Nov 12 '18 at 3:43
JarackJarack
34
Hi I am a student in a Java course and we just covered Big-O notation.
I understand the general picture of Big-O, where it takes the worst-case scenario, and then it calculates the efficiency of the code, and I understand the general run-times of each process. I can say that the run-time of the code below is O(n^2).
What I am having trouble with is calculating the polynomials. Right now, I just look at a code snippet and know the efficiency, but I do not know the snippet's f(x) or its reference function (g(x)).
Could I get help with finding the f(x) and g(x) for the following code? (only the process for finding the answer is necessary, exact answers not needed)
Links to documents or videos that deal with this topic would also be helpful. Thanks!
public static int num_occurrences(int n)
int count = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if ( i == j )
continue;
if (strings[i] == strings[j])
count++;
return count;
java big-o polynomials
java big-o polynomials
edited Nov 12 '18 at 4:26
suvojit_007
1,3251517
asked Nov 12 '18 at 3:43
JarackJarack
34
edited Nov 12 '18 at 4:26
suvojit_007
1,3251517
asked Nov 12 '18 at 3:43
JarackJarack
34
edited Nov 12 '18 at 4:26
suvojit_007
1,3251517
edited Nov 12 '18 at 4:26
suvojit_007
1,3251517
edited Nov 12 '18 at 4:26
suvojit_007
1,3251517
1,3251517
asked Nov 12 '18 at 3:43
JarackJarack
34
asked Nov 12 '18 at 3:43
JarackJarack
34
asked Nov 12 '18 at 3:43
JarackJarack
34
34
closed as off-topic by Stephen C, gnat, EdChum, Unheilig, V-rund Puro-hit Nov 12 '18 at 9:58
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – Stephen C, EdChum, V-rund Puro-hit
closed as off-topic by Stephen C, gnat, EdChum, Unheilig, V-rund Puro-hit Nov 12 '18 at 9:58
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – Stephen C, EdChum, V-rund Puro-hit
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
For each and every value of i , the inner loop is running exactly n times.
When i=0 , j = 0,1,....,n-1 (n times)
When i=1 , j = 0,1,....,n-1 (n times) .......and so on
Therefore, the total number of steps is: n + n + n + n + n+ ......+ n = n*n = n^2
So the runtime will be O(n^2)
You might want to see Time complexity of nested for-loop
Edit:
for(int i = 0; i < n; i++) //<---- cost A*n^2 time
for(int j = 0; j < n; j++)
if ( i == j )
continue;
if (strings[i] == strings[j])
count++;
return count; //<---- cost constant time
We have f(x) = Ax^2 + C
Nested loop operation will cost Ax^2 and return statement would also cost some constant time say C
answered Nov 12 '18 at 4:35
suvojit_007suvojit_007
1,3251517
I am asking a little bit different of a question than this I think. The link helped a little, but my question is: how do i get the f(x) of the code snippet above? I know that the effieciency is O(n^2).
– Jarack
Nov 12 '18 at 6:17
f(x)is often the runtime of the algorithm so you can find it by the above calculation.
– suvojit_007
Nov 12 '18 at 6:25
I do not see how we would get the following form: f(x) = Ax^2 + Bx + C from the above calculation, would you mind elaborating further?
– Jarack
Nov 12 '18 at 7:49
@Jarack check the updated answer
– suvojit_007
Nov 12 '18 at 8:07
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
For each and every value of i , the inner loop is running exactly n times.
When i=0 , j = 0,1,....,n-1 (n times)
When i=1 , j = 0,1,....,n-1 (n times) .......and so on
Therefore, the total number of steps is: n + n + n + n + n+ ......+ n = n*n = n^2
So the runtime will be O(n^2)
You might want to see Time complexity of nested for-loop
Edit:
for(int i = 0; i < n; i++) //<---- cost A*n^2 time
for(int j = 0; j < n; j++)
if ( i == j )
continue;
if (strings[i] == strings[j])
count++;
return count; //<---- cost constant time
We have f(x) = Ax^2 + C
Nested loop operation will cost Ax^2 and return statement would also cost some constant time say C
answered Nov 12 '18 at 4:35
suvojit_007suvojit_007
1,3251517
I am asking a little bit different of a question than this I think. The link helped a little, but my question is: how do i get the f(x) of the code snippet above? I know that the effieciency is O(n^2).
– Jarack
Nov 12 '18 at 6:17
f(x)is often the runtime of the algorithm so you can find it by the above calculation.
– suvojit_007
Nov 12 '18 at 6:25
I do not see how we would get the following form: f(x) = Ax^2 + Bx + C from the above calculation, would you mind elaborating further?
– Jarack
Nov 12 '18 at 7:49
@Jarack check the updated answer
– suvojit_007
Nov 12 '18 at 8:07
add a comment |
For each and every value of i , the inner loop is running exactly n times.
When i=0 , j = 0,1,....,n-1 (n times)
When i=1 , j = 0,1,....,n-1 (n times) .......and so on
Therefore, the total number of steps is: n + n + n + n + n+ ......+ n = n*n = n^2
So the runtime will be O(n^2)
You might want to see Time complexity of nested for-loop
Edit:
for(int i = 0; i < n; i++) //<---- cost A*n^2 time
for(int j = 0; j < n; j++)
if ( i == j )
continue;
if (strings[i] == strings[j])
count++;
return count; //<---- cost constant time
We have f(x) = Ax^2 + C
Nested loop operation will cost Ax^2 and return statement would also cost some constant time say C
answered Nov 12 '18 at 4:35
suvojit_007suvojit_007
1,3251517
I am asking a little bit different of a question than this I think. The link helped a little, but my question is: how do i get the f(x) of the code snippet above? I know that the effieciency is O(n^2).
– Jarack
Nov 12 '18 at 6:17
f(x)is often the runtime of the algorithm so you can find it by the above calculation.
– suvojit_007
Nov 12 '18 at 6:25
I do not see how we would get the following form: f(x) = Ax^2 + Bx + C from the above calculation, would you mind elaborating further?
– Jarack
Nov 12 '18 at 7:49
@Jarack check the updated answer
– suvojit_007
Nov 12 '18 at 8:07
add a comment |
For each and every value of i , the inner loop is running exactly n times.
When i=0 , j = 0,1,....,n-1 (n times)
When i=1 , j = 0,1,....,n-1 (n times) .......and so on
Therefore, the total number of steps is: n + n + n + n + n+ ......+ n = n*n = n^2
So the runtime will be O(n^2)
You might want to see Time complexity of nested for-loop
Edit:
for(int i = 0; i < n; i++) //<---- cost A*n^2 time
for(int j = 0; j < n; j++)
if ( i == j )
continue;
if (strings[i] == strings[j])
count++;
return count; //<---- cost constant time
We have f(x) = Ax^2 + C
Nested loop operation will cost Ax^2 and return statement would also cost some constant time say C
answered Nov 12 '18 at 4:35
suvojit_007suvojit_007
1,3251517
For each and every value of i , the inner loop is running exactly n times.
When i=0 , j = 0,1,....,n-1 (n times)
When i=1 , j = 0,1,....,n-1 (n times) .......and so on
Therefore, the total number of steps is: n + n + n + n + n+ ......+ n = n*n = n^2
So the runtime will be O(n^2)
You might want to see Time complexity of nested for-loop
Edit:
for(int i = 0; i < n; i++) //<---- cost A*n^2 time
for(int j = 0; j < n; j++)
if ( i == j )
continue;
if (strings[i] == strings[j])
count++;
return count; //<---- cost constant time
We have f(x) = Ax^2 + C
Nested loop operation will cost Ax^2 and return statement would also cost some constant time say C
answered Nov 12 '18 at 4:35
suvojit_007suvojit_007
1,3251517
edited Nov 12 '18 at 8:06
answered Nov 12 '18 at 4:35
suvojit_007suvojit_007
1,3251517
answered Nov 12 '18 at 4:35
suvojit_007suvojit_007
1,3251517
answered Nov 12 '18 at 4:35
suvojit_007suvojit_007
1,3251517
1,3251517
I am asking a little bit different of a question than this I think. The link helped a little, but my question is: how do i get the f(x) of the code snippet above? I know that the effieciency is O(n^2).
– Jarack
Nov 12 '18 at 6:17
f(x)is often the runtime of the algorithm so you can find it by the above calculation.
– suvojit_007
Nov 12 '18 at 6:25
I do not see how we would get the following form: f(x) = Ax^2 + Bx + C from the above calculation, would you mind elaborating further?
– Jarack
Nov 12 '18 at 7:49
@Jarack check the updated answer
– suvojit_007
Nov 12 '18 at 8:07
add a comment |
I am asking a little bit different of a question than this I think. The link helped a little, but my question is: how do i get the f(x) of the code snippet above? I know that the effieciency is O(n^2).
– Jarack
Nov 12 '18 at 6:17
f(x)is often the runtime of the algorithm so you can find it by the above calculation.
– suvojit_007
Nov 12 '18 at 6:25
I do not see how we would get the following form: f(x) = Ax^2 + Bx + C from the above calculation, would you mind elaborating further?
– Jarack
Nov 12 '18 at 7:49
@Jarack check the updated answer
– suvojit_007
Nov 12 '18 at 8:07
I am asking a little bit different of a question than this I think. The link helped a little, but my question is: how do i get the f(x) of the code snippet above? I know that the effieciency is O(n^2).
– Jarack
Nov 12 '18 at 6:17
I am asking a little bit different of a question than this I think. The link helped a little, but my question is: how do i get the f(x) of the code snippet above? I know that the effieciency is O(n^2).
– Jarack
Nov 12 '18 at 6:17
f(x) is often the runtime of the algorithm so you can find it by the above calculation.– suvojit_007
Nov 12 '18 at 6:25
f(x) is often the runtime of the algorithm so you can find it by the above calculation.– suvojit_007
Nov 12 '18 at 6:25
I do not see how we would get the following form: f(x) = Ax^2 + Bx + C from the above calculation, would you mind elaborating further?
– Jarack
Nov 12 '18 at 7:49
I do not see how we would get the following form: f(x) = Ax^2 + Bx + C from the above calculation, would you mind elaborating further?
– Jarack
Nov 12 '18 at 7:49
@Jarack check the updated answer
– suvojit_007
Nov 12 '18 at 8:07
@Jarack check the updated answer
– suvojit_007
Nov 12 '18 at 8:07
add a comment |
