Skip to main content
added 1 character in body
Source Link
zkutch
  • 2.4k
  • 1
  • 8
  • 14

Most simple example gives nested cycles: we nowknow that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.

Hence, every 4 nested loops gives complexity $O(n^4)$, $k$ nested loops $O(n^k)$.

Another examples Karmarkar's algorithm, AKS primality test

Most simple example gives nested cycles: we now that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.

Hence, every 4 nested loops gives complexity $O(n^4)$, $k$ nested loops $O(n^k)$.

Another examples Karmarkar's algorithm, AKS primality test

Most simple example gives nested cycles: we know that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.

Hence, every 4 nested loops gives complexity $O(n^4)$, $k$ nested loops $O(n^k)$.

Another examples Karmarkar's algorithm, AKS primality test

added 195 characters in body
Source Link
zkutch
  • 2.4k
  • 1
  • 8
  • 14

Most simple example gives nested cycles: we now that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.

Hence, every 4 nested loops gives complexity $O(n^4)$, $k$ nested loops $O(n^k)$.

Another examples Karmarkar's algorithm, AKS primality test

Most simple example gives nested cycles: we now that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.

Hence, every 4 nested loops gives complexity $O(n^4)$.

Most simple example gives nested cycles: we now that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.

Hence, every 4 nested loops gives complexity $O(n^4)$, $k$ nested loops $O(n^k)$.

Another examples Karmarkar's algorithm, AKS primality test

Source Link
zkutch
  • 2.4k
  • 1
  • 8
  • 14

Most simple example gives nested cycles: we now that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.

Hence, every 4 nested loops gives complexity $O(n^4)$.