Example1:
This I would say is O(log(n)), my reasoning is that if we choose a test n, n = 10, then 'i' would run: 0,2,4,6,8,10, so 'i' is behaving linearly not growing but just adding + 2 each time it iterates. And the method is also 'n' - dependent meaning that as n grows so does the method. So the first loop is O(n), then the second loop goes, if we choose n test to be n = 10, then after each iteration 'j' would run: 2,4,8,16,32,64 then can be thought of as 2^n which is a logarithmic function, so this loop is logarithmic. So computing this: O(n)*O(log(n)) = O(log(n))
for (i = 0; i < n; i = i + 2) {
for ( i = 1; j <= n; j = j*2) {
System.out.println("Hi");
}
}
Example2:
for this one if we choose n to be n = 10, then 'i' runs: 2,4,8,16,32 again can be rewritten as 2^n, this is logarithmic, O(log(n))
for (i = 1; i < n; i = i + i) {
System.out.println("Soda");
}
Example3:
for this one the first loop is n-dependent, the method changes as n grows, nothing fancy with 'i' it simply adds +1 so this is a n-dependent loop of O(n) for any inputted n. if the number is even it runs the first nested loop, if the number is positive it runs the second nested loop. The first inner loop is the same complexity, O(n). and the last inner loop is (I think, despite n*n) O(n). So computing this we get: O(n)*O(n) = O(n^2) if the if-statement is true, and O(n)*O(n) if the if statement is false, so in the worst case it is O(n^2) because we multiply the two O(n)'s.
for (i = 0; i < n; i++) {
if (i % 2 == 0) {
for (j = 0; j < n; j++) {
System.out.println("Rawr");
}
} else {
for (j = 0; j < n*n; j++) {
System.out.println("Computer");
}
}
Have I made errors? please explain Thank you
