Why O(logm + logn) and not O(logm * logn) [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 9 years ago.

Improve this question

I saw the same question 3 times on Stack Overflow: Complexity of an algorithm Time complexity for two pieces of code Tricky Big-O complexity

I wanted to ask the question in one of them but I couldn't since I'm new on the website and can't comment.

Can someone please explain to me why the complexity is O(logm + logn) and not O(logm * logn)? I tried solving it myself and O(logm * logn) makes more sense to me... since if for example you run it with n=16 and m=1000 then you get about 6 + 4... and it makes more sense that it'll run 6 * 4 times ...

Can you please clarify it for me..? Thanks :)

Answer 1

Well, the while loop runs in O(logm), where the log has a base of 3 and after the while loop, the outer for loop runs a constant number of times <= 100, and the inner for loop runs in O(logn), where the log has a base of 2.

Because it runs in O(1), the outer for loop can be ingnored( complexity means ignoring the constants and studying growth, not the number of steps in which an algorithm executes! ); the algorithm has O(logm + logn) complexity because first you have the while in O(logm) and after that the for in O(logn)( you do nat have the for inside the while to multiply them ).

Answer 2

while and for loops are two seperate loops. for is not inner loop. The code is like this

while (i>100){
    i = i/3;
} //end of while

for (int k=i; k>=0; k--){
    for (int j=1; j<n; j*=2)
        System.out.print(k + "\t" + j);
    System.out.println();
} //end of for

Since they are separate, result should be summed, not multiplied