0

How should I go about determining the upper bound of the complexity of these code snippets in terms of big O? I'm just learning about these concepts and am looking for : clues, straight-out responses, best resources on learning more.

I found this other thread, but i'm still having trouble adapting the answer.

I'm given these examples:

For J = 1 to 10000000000000
    C[J] = A[J] + B[J]



For J = 1 to N
    C[J] = A[J] * B[J]



For J = 1 to N
    For K = 1 to N
        C[J][K] = A[J] * B[K]


For I = 1 to N
    For J = 1 to 10000000000000
        For K = 1 to N
            C[I][J] = A[J][K] * B[K][I]
Community
  • 1
  • 1
user25976
  • 1,005
  • 4
  • 18
  • 39

1 Answers1

2

Big O says what is the relationship between the input size and the time/space complexity.

Now onto your examples:

  • For J = 1 to 10000000000000 - The 10000000000000 is just a constant. Even though it is a big number, it doesn't depend on the input size (N), which is why this is O(1)
  • For J = 1 to N - The number of iterations now directly depends on N, this is said to be linear complexity, since if you increase N by one, the loop will run one more time.
  • Two nested loops - since they both depend on N, the complexity is O(N * N)

The last one is easy to figure out knowing the above.

Jakub Arnold
  • 85,596
  • 89
  • 230
  • 327
  • Just checking for comprehension: For the last one, considering that the 10000000000000 is constant, even if there are three for loops it would still just be O(N*N)? Also, why do we multiply the Ns? – user25976 Nov 23 '14 at 01:21
  • @user25976 Yes it would be just O(N*N), or O(N^2) ... as in N squared. – Jakub Arnold Nov 23 '14 at 15:44
  • @user25976 We multiply the Ns because the inner loop executes N times for each iteration of the outer loop. The outer loop executes N times as well, which gives us N*N. – Jakub Arnold Nov 23 '14 at 15:45
  • Would it still be multiplied if the second two loops are on the same level? – user25976 Dec 07 '14 at 03:34
  • No, in that case it would equal to 2*O(N), which is asymptotically still O(N). – Jakub Arnold Dec 07 '14 at 14:39