CODEWITHSUNDEEP
algorithmcomplexity-theorybig-o
Sergej Popov
Sergej Popov

Reputation: 3021

logarithmic complexity represented with loop?

as far as I got it linear complexity can be represented as simple loop and quadratic complexity can be represented as nested loop. How can the cubic and logarithmic complexity be represented?

Thanks!

Upvotes: 6

Views: 4230

Answers (5)

mishadoff
mishadoff

Reputation: 10789

Cubic complexity - three nested loops:

foreach
   foreach
      foreach
      // actions
      end
   end
end

Logarithm complexity example - binary search.

Upvotes: 1

wannik
wannik

Reputation: 12706

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

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

Upvotes: 0

Paul R
Paul R

Reputation: 212979

A simple loop can have logarithmic complexity, e.g.

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

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

Upvotes: 9

sll
sll

Reputation: 62504

  • Cubic - three nested loops
  • Logarithmic - the idea that on each loop cycle you are splitting input data set by parts (or somehow makes it smaller) and in the next cycle process shortened data set, so basically complexity does not growth significantly whilst input data set growth. For instance take a look at the BinarySearch algorithm or any an other Divide and conquer algorithm.

Upvotes: 1

Tudor
Tudor

Reputation: 62439

Since cubic is O(n^3), it would be three nested loops.

Logarithmic is not so straightforward and usually requires a recursive relation. For example, MergeSort is O(n*log(n)) because it forms a recursion tree of height log(n) and each level requires an O(n) merging operation.

Upvotes: 5

Related Questions