Logarithmic Time Complexity

Question

For this algorithm, would the Time Complexity or Big O of N be O(n), O(log n) or something else?

Code here:

int i = 1;

while(i*i <= n){

    System.out.println(i);
    i += 2;

}

The loop iterates approximately sqrt(n) / 2 times, therefore its complexity is O(sqrt(n)). — xunatai, Jun 14 '17 at 05:06

score 0 · Answer 1 · answered Jun 14 '17 at 06:10

0

Please look into examples provided in What does O(log n) mean exactly? and on wiki page Linear_time. There is good explanation how to count complexity. According to it your algorithm complexity would be O(n), because you have one loop, which depends on provided 'n' variable.

answered Jun 14 '17 at 06:10

Wujek Samo Zło

56
3

But the number of times this algorithm runs is also based on i*I being less than or equal to n, and i increases by 2 each time. – Makasulee Jun 14 '17 at 09:20

Logarithmic Time Complexity

1 Answers1