Is the logarithmic complexity represented by a loop?

Question

as I understand it, linear complexity can be represented as a simple loop, and quadratic complexity can be represented as a nested loop. How can you imagine cubic and logarithmic complexity?

Thanks!

Answer 1

A simple loop can have logarithmic complexity, for example

for (i = 1; i <= N; i *= 2) ... 

As others have said, a triple nested loop will have cubic complexity.

Answer 2

Since the cube is O (n ^ 3), it will be three nested loops.

Logarithmic is not so simple and usually requires a recursive relationship. For example, MergeSort is O (n * log (n)), because it forms a recursion tree with a height of log (n), and merge operation O (n) is required for each level.

Answer 3

• Cubic - three nested loops
• Logarithmic is the idea that on each cycle of the cycle you break the input data specified in parts (or somehow reduce them), and in the next cycle - a reduced data set, so basically the complexity does not increase significantly, and the input data grows increases. For example, look at the BinarySearch algorithm or any other Divide and Win .

Answer 4

Cubic complexity - three nested cycles:

 foreach foreach foreach // actions end end end 

An example of logarithm complexity is binary search .

Answer 5

O (n ^ 3) can be represented by three nested loops.

O (log n) is represented by a cycle in which each iteration, the amount of data that needs to be processed, is reduced by half.