Algorithm complexity

I am studying a test and see this question, so I did the following: is this correct?

while loop runs at point O (log3n).

the for loop works roughly with O ((n- (some math)) * log2n), since I have a minus sign that is linear, I say that the whole method works in O (nlogn), if I'm not wrong, and it's something like

O ((n- (n / log3n)) * log2n) <- not quite, but quite, cannot understand this.

Is minus linear here or not? if not what is right 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();
    }
}
+4
source share
2 answers

While loop works in O(logm).

while i <= 100, 100 .

O(logn) , . , O(logm + 100*logn)= O(logm + logn).

+1

while O(100*log_3(m)). .

for , i 100 (- while), O(100*log_2(n)), O(log_3(m) + log_2(n)).

0

Source: https://habr.com/ru/post/1534436/


All Articles