Complexity of an algorithm

Question

I'm studying for a test and saw this question , so I did the following, is it correct?

the while loop runs at O(log3n).

the for loop runs at about O((n-(some math))*log2n) so because I have the minus symbol which is linear, I say that the whole method runs at O(nlogn), unless I'm wrong and it's something like

O((n-(n/log3n))*log2n) <- not exactly but quite, can't really figure it out.

is the minus linear here or not? if not what is the correct bigO?

public void foo (int n, int m)
{
    int i = m;
    while (i>100)
     i = i/3;
    for (int k=i; k>=0; k--)
    {
        for (int j=1; j<n; j*=2)
         System.out.print(k + "\t" + j);
        System.out.println();
    }
}

why do you care about the minus ? the expression within parentheses apriori cannot be less than zero, hence the first term is larger-equal than the second term and hence you may use the first term which asymptotically goes to O(nlogn). unless you made a mistake while calculating this: O((n-(n/log3n))*log2n) — mangusta
– mangusta, Commented Apr 1, 2014 at 12:34

fgb · Accepted Answer · 2014-04-01 12:36:49Z

1

The while loop runs in O(logm).

After the while loop has finished, i is <= 100, so the next for loop will run at most 100 times.

The inner loop will run O(logn) times, for each iteration of the outer loop. So total time is O(logm + 100*logn) = O(logm + logn).

edited Apr 1, 2014 at 12:36

answered Apr 1, 2014 at 12:31

fgb

18.6k3 gold badges41 silver badges52 bronze badges

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

3 Comments

Seth Keno Over a year ago

can you please explain me why it's not - O((n/(n/100))*logn)? m/(m/100) will give me 100 for every m > 100 (which is the worse case), and im looping m/(m/100) times over log2n.

Seth Keno Over a year ago

I think I answered my own question... if m/(m/100) is always 100 for m>100, I'm basically saying the bigO is O(100*logn) which is O(logn), can I substract the logn from the bigO you wrote (since log2n is bigger than log3m) and just make it O(log3m)?

fgb Over a year ago

@SethKeno The number of times the first loop runs is dependent on m. It's not always 100 for m > 100. I don't see why you're dividing by m. Increasing m will increase the total time because of the first loop so it has to be in the final expression.

Filipe Gonçalves · Accepted Answer · 2014-04-01 12:32:22Z

0

The first while loop runs in O(100*log_3(m)). This should be easy to see.

For the outer for loop, note that i is at most 100 (because of the previous while loop), and the inner loop is O(100*log_2(n)), so the overall asymptotic limit is O(log_3(m) + log_2(n)).

answered Apr 1, 2014 at 12:32

Filipe Gonçalves

21.3k6 gold badges58 silver badges74 bronze badges

2 Comments

Bernhard Barker Over a year ago

Indicating the base for logs is redundant inside big-O notation.

Filipe Gonçalves Over a year ago

@Dukeling I know. It was just to make the maths clearer for the OP, to make him see where it comes from. But thanks for the feedback.

Collectives™ on Stack Overflow

Complexity of an algorithm

2 Answers 2

3 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related