CODEWITHSUNDEEP
c++algorithmperformance
amchacon
amchacon

Reputation: 1961

Cost of an algorithm

The problem is the next:

We want to know the size of an vector, we can't use size() but we have a function inBounds(vector& arr,int index) that returns true if the index is a valid position of the vector.

So, my approach is iterate positions. Starting at 1 and duplicating (2,4,8,16,32...) until that inBounds returns false, step back so and repeat the search in the subrange.

Let's do an example, put N = 21:

Step back to 16, and search in 16-32 range:

Step back to 20 (16+4) and start over:

Start over in 21:

Ok, so the size is 21.

This is my implementation in code:

#include <iostream>
#include <vector>
using namespace std;

int inBounds(const vector<int>& arr,int i)
{
    return i < arr.size();
}

int size(const vector<int>& arr)
{
    int init = 0;

    while (inBounds(arr,init))
    {
        int start = 2;
        while (inBounds(arr,init+start))
        {
            start *= 2;
        }
        start /= 2;
        init += start;
    }
    return init;
}


int main()
{
    vector<int> arr;

    for (int i = 0;i < 1000;i++)
    {
        arr.resize(i);
        int n = size(arr);
        if (n != arr.size())
            cout << "FAIL " << arr.size() << ' ' << n << endl;
    }
    return 0;
}

This works good. But i don't know the exactly cost of this algorithm. The first search is indeed log(N), but now i need to add the subrange searchs. So i have my doubts about the real cost

Upvotes: 0

Views: 200

Answers (4)

Adrian Colomitchi
Adrian Colomitchi

Reputation: 3992

Actually, your worst case scenario is O(log(n)2) (which is sorta expected, since you have a O(log) cycle nested inside another log cycle)

To understand why, try to narrow down 31 (2N-1 in the general case)

Let's do an example, put N = 31:

1 = True
2 = True
4 = True
8 = True
16 = True
32 = False

O(log(N)) to here, alright, nobody contests it

--

Now count the extra steps

Step back to 16, and search in 16-32 range:

(16+1) = True
(16+2) = True
(16+4) = True
(16+8) = True
(16+16) = False

(4+1) steps - which is log(32/2)+1 = log(32)

Step back at 24

(24+1) = True
(24+2) = True
(24+4) = True
(24+8) = False

(3+1) steps - which is log(16/2)+1=log(16)

Step back at 28:

(28+1) = True
(28+2) = True
(28+4) = False

(2+1) steps - which is log(8/2)+1=log(8)

Step back at 30

(30+1) = True
(30+2) = False

(1+1) steps which is log(4/2)+1=log(4)

Result: (4+3+2+1=10 steps in positive + 4 in negative). Or, in another form log(32)+log(16)+log(8)+log(4)+log(2) - 1 =log(32)(1+1/2+1/3+1/4+1/5)-1. Ignore the -1 at the end and your formula becomes something like

log(N)*(1+1/2+1/3+1/4+...+1/N)

Well, for large N-es, the harmonic series is divergent and the asymptotic behaviour is logarithmic.

So you got yourself a nice O(log(N)*log(N)) complexity.

QED(??)

Upvotes: 3

Shasha99
Shasha99

Reputation: 1916

Suppose the size of the vector is N = 31. Since this is going to be the worst case for the your algorithm here is how it will work:

first pass : 1,2,4,8,16,32            [ total = 6 ]
second pass: 17,18,20,24,32           [ total = 5 ]
third pass : 25,26,28,32              [ total = 4 ]
forth pass : 29,30,32                 [ total = 3 ]
fifth pass : 31                       [ total = 1 ]

If we talk in terms on N. it would be:

T(N) = logN*(1+1/2+1/4+1/8+....)

which is of order: (logN)^2

You should actually consider the approach given by @celtschk which is O(logN)

Upvotes: 1

celtschk
celtschk

Reputation: 19721

Once you've found the upper bound, you really should do a binary search. Applying to your example:

  • Result of initial loop: 16 → true, 32 → false, so size in (16, 32]

The binary search always tests the middle between the largest found true and the smallest found false:

  • 24 → false => (16, 24]
  • 20 – true => (20, 24]
  • 22 → false => (20, 22]
  • 21 → false => (20, 21]

So the size is 21.

Note that this needed only 4 additional tests, as opposed to 7 for your algorithm.

Upvotes: 1

matias elgart
matias elgart

Reputation: 1181

seems like your first subrange search is also logN (since it uses basically same algorithm as the initial part) while your final subrange search is linear (iterating over every value), but it's very much bounded and a small fraction of N. i would say your algorithm is roughly c * logN, where c is a small value representing the number of subsearches you're doing, so O(logN) in general.

Upvotes: 1

Related Questions