3 replies to this topic

[Pillager]

Hi guys, I was wondering if anyone could give me any tips on these exercises I am trying.

I'm trying to make an algorithm that runs proportional to O(log(n²)).

The attempt I've coded (in java) looks something like this:

int count = 0;


for(int i=1; i<n; i*=2) {


  for(int j=0; j<n; j++) {


    for(int k=0; k<n; k++) {


     count++; }}}

Now from my understanding I thought that the two inner loops would give an N² complexity, which would then be multiplied by the outer loop which has a log complexity. I assume something fairly fundamental is tripping me up, I suspect either the order of my loops or a math error based on the log part.

Anyway thanks for any advice you can give, feel free to give any general tips on algorithm analysis if you want as I think I only have a vague grasp on the topic.

[morefood2001]

This algorithm is an N^3 algorithm.

To get logarithm time, you need recursion so that you only hit a fraction of the total number of values. Tree data structures are good at getting logarithmic time.

For example, if you have 5 elements, you will only touch through 4 of them.

[WingedPanther]

O(log(n^2)) is actually O(2*log(n)) or O(log(n)). A typical algorithm of this complexity is a binary search.

[John]

The "number guessing game" is generally a good example of an O(log(n)) algorithm.