Algorithm analysis (big-O) for algorithm

Question

I'm trying to help a friend analyze the complexity of his algorithm but my understanding of Big-O notation is quite limited.

The code goes like this:

int SAMPLES = 2000;
int K_SAMPLES = 5000;

int i = 0; // initial index position    
while (i < SAMPLES)
{
    enumerate();                       // Complexity: O(SAMPLES)
    int neighbors = find_neighbors(i); // Complexity: O(1) 

    // Worst case scenario, neighbors is the same number of SAMPLES
    int f = 0;
    while (f < neighbors) // This loop is probably O(SAMPLES) as well.
    {
        int k = 0; // counter variable
        while (k < K_SAMPLES) // Not sure how to express the complexity of this loop.
        {                     // Worst case scenario K_SAMPLES might be bigger than SAMPLES. 

            // do something!

            k++;
        }
        f++;
    }

    i++;
}

There are 2 functions inside the code but I was able to identify their complexity since they are simple. However, I was unable to express the complexity of the inner while loop, but even after it is measured, I still need help to assemble all these complexities into a formula that represents the computational complexity of the algorithm.

I seriously need help on this matter. Thanks!

while (i < neighbors) won't this loop infinitely? i and neighbors are not modified. — nhahtdh
– nhahtdh, Commented Mar 5, 2013 at 20:50
What are the variables here? Is N the only variable? I'm guessing N represents the set of all neighbors. Do you assume SAMPLES and K_SAMPLES to be fixed? Because then they wont even matter when calculating the big-O. — Daniel Williams
– Daniel Williams, Commented Mar 5, 2013 at 20:53
What is n? Which of these inputs are variable? You may need to express it in terms of multiple variables if, for example, SAMPLES and K_SAMPLES vary independently of one another. — Aaron Dufour
– Aaron Dufour, Commented Mar 5, 2013 at 21:42
I meant to write O(SAMPLES) and not O(n). Thanks for pointing that out! — karlphillip
– karlphillip, Commented Mar 6, 2013 at 4:12

DPenner1 · Accepted Answer · 2013-03-06 07:10:47Z

3

Worst case analysis going from inner most loop to outer most (with mild abuse of the "=" sign):

->  O(K_SAMPLES)                    -- complexity of just the k-loop

->  neighbors * O(K_SAMPLES)         -- complexity of f-loop accounted for
 =  SAMPLES * O(K_SAMPLES)          -- since neighbors = SAMPLES in worst case
 =  O(SAMPLES * K_SAMPLES)

->  O(SAMPLES) + O(SAMPLES * K_SAMPLES)  -- adding complexity of enumerate()
 =  O(SAMPLES + SAMPLES * K_SAMPLES)
 =  O(SAMPLES * K_SAMPLES)

The SAMPLES term was dropped since SAMPLES * K_SAMPLES grows asymptotically faster. More formally,

When C >= 2, SAMPLES >= 1, K_SAMPLES >= 1 then

SAMPLES + SAMPLES * K_SAMPLES  <=  C(SAMPLES * K_SAMPLES)
SAMPLES * (K_SAMPLES + 1)  <=  SAMPLES * C * K_SAMPLES
K_SAMPLES + 1  <=  C * K_SAMPLES

For more info on big-O with multiple variables, see here. Continuing on with the last loop we have:

->  SAMPLES * O(SAMPLES * K_SAMPLES)    -- complexity of i-loop accounted for
 =  O(SAMPLES^2 * K_SAMPLES)

Note that depending on the average number returned by find_neighbors(i), it can make the average big-O different.

edited Mar 6, 2013 at 7:10

answered Mar 6, 2013 at 6:39

DPenner1

10.6k5 gold badges34 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

karlphillip Over a year ago

+1 For abuse. Kidding aside, the answer looks good. I wish somebody else could evaluate it too so I can close the thread.

WestCoastProjects · Accepted Answer · 2013-03-05 20:52:10Z

0

O(neighbors * K_SAMPLES)

if neighbors << K then this is closer to linear in K_SAMPLES

If neighbors on order of K_SAMPLES this is quadratic in K_SAMPLES

answered Mar 5, 2013 at 20:52

WestCoastProjects

63.9k109 gold badges368 silver badges636 bronze badges

Collectives™ on Stack Overflow

Algorithm analysis (big-O) for algorithm

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related