Algorithm complexity

Question

What is the difficulty given for the following problem: O (n). Shouldn't it be O (N ^ 2)? Is it because the outer loop is O (n), and the inner is also O (n), so n * n = O (n ^ 2)?

The answer sheet for this question indicates that the answer is O (n). How is this possible?

public static void q1d(int n) { int count = 0; for (int i = 0; i < n; i++) { count++; for (int j = 0; j < n; j++) { count++; } } } 

The complexity for the next task is O (n ^ 2), how can you get it? Can someone comment?

 public static void q1E(int n) { int count = 0; for (int i = 0; i < n; i++) { count++; for (int j = 0; j < n/2; j++) { count++; } } } 

thanks

Answer 1

The first example is O(n^2) , so it seems they made a mistake. To calculate (informally) the second example, we can do n * (n/2) = (n^2)/2 = O(n^2) . If that doesn't make sense, you need to go and freshen up, which means something that is O(n^k) .

Answer 2

The complexity of both codes is O (n * n)

FIRST

The outer loop runs n times, and the inner loop changes from 0 to n-1 times

So

total = 1 + 2 + 3 + 4 ... + n

which, if you add an arithmetic progression, n * ( n + 1 ) / 2 is O(n*n)

SECOND

The outer loop runs n times, and the inner loop changes from 0 to n-1/2 times

So

total = 1 + 1/2 + 3/2 + 4/2 ... + n/2

which if you add an arithmetic progression, n * ( n + 1 ) / 4 also O(n*n)

Answer 3

The first case is definitely O(n^2)

The second is O(n^2) , since you omit the constants when calculating large O

Answer 4

Your answer sheet is incorrect, the first algorithm is clearly O (n ^ 2).

The Big-Oh designation is the “worst case”, so when calculating the Big-Oh value, we usually ignore multiplication / division by constants.

Moreover, your second example is also O (n ^ 2) in the worst case, because although the inner loop is “only” 1/2 n, n is a clear limiting factor. In practice, the second algorithm will have fewer O (n ^ 2) operations, but Big-Oh is designed to measure the “worst case” (ie Maximum Limit), so the exact number of operations is ignored in favor of focusing on how the algorithm works when n is approaching infinity.

Answer 5

Both are O(n^2) . Your answer is incorrect. Or you may have asked the wrong question.