Revisions to How to properly calculate dependent nested loops for big-O [duplicate]

Post Closed as "Duplicate" by Evil, xskxzr, David Richerby, Discrete lizard♦, Juho

Is there a system behind the magic of algorithm analysis?

occurred Jan 18, 2019 at 8:00

added 8 characters in body

Source Link

edited Dec 24, 2018 at 11:53

279.1k
27
316
512

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array   
For i = 0; i < n; i++:
        For j = 0; j < i; j++:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $1/2n(n+1)$$\frac{1}{2}n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array   
For i = 0; i < n; i++:
        For j = 0; j < i; j++:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $1/2n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array   
For i = 0; i < n; i++:
        For j = 0; j < i; j++:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $\frac{1}{2}n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

edited body

Source Link

edited Dec 23, 2018 at 19:32

Confuto

123
1
4

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array   
For i = 1;0; i < n; i++:
        For j = 1;0; j < i; j++:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $1/2n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array   
For i = 1; i < n; i++:
        For j = 1; j < i; j++:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $1/2n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array   
For i = 0; i < n; i++:
        For j = 0; j < i; j++:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $1/2n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

added 20 characters in body

Source Link

edited Dec 23, 2018 at 19:30

Confuto

123
1
4

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array   
whileFor i = 1; i < nn; i++:
        whileFor j = 1; j < ii; j++:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $1/2n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array   
while i < n:
        while j < i:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $1/2n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array   
For i = 1; i < n; i++:
        For j = 1; j < i; j++:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $1/2n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

Source Link

asked Dec 23, 2018 at 18:54

Confuto

123
1
4

Loading

Stack Exchange Network

Return to Question