CODEWITHSUNDEEP
algorithmbig-otime-complexity
user3011240
user3011240

Reputation: 97

Why is the algorithmic complexity of this code 1/2n^2 + n + 1?

For the following code:

  print a

  for (i = 0; i < n; i++)
    for (j = i; j < n; j++)
      print b

Obviously, the big oh of n for print a is just 1, but I don't understand how the second part is 1/2n + 1/2n^2.

The first for loop represents n and then the second for loop represents (1/2 + 1/2n) I guess?

Upvotes: 0

Views: 289

Answers (4)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

If you're comfortable with discrete mathematics, going step-by-step using Sigma notation would let you see the sought result as such:

enter image description here

Upvotes: 0

omer681
omer681

Reputation: 66

The outer loop runs n times.

The inside loop runs n, n-1, n-2, ..., 1 times.

The complexity of the code inside the loop is O(1) so the total complexity is:

n + n-1 + n-2 + ... + 1 = n(n+1)/2 = (1/2)n^2 + (1/2)n = (n^2)/2 + n/2 = O(n^2)

Upvotes: 3

tonga
tonga

Reputation: 11981

In the for loops, the total number of time that the print statement is called can be calculated by

n + (n-1) + (n-2) + ... + 1

which sums to n(n+1)/2. So the big O notation for this complexity should be O(n^2).

Upvotes: 0

chrk
chrk

Reputation: 4215

For i = 0, print will be executed n times.

For i = 1, print will be executed n-1 times.

For i = 2, print will be executed n-2 times.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

For i = n - 1, print will be executed 1 time.

Summing up, print will be executed n + n-1 + n-2 + ... + 1 times.

Thus, the complexity is O(n^2).

Upvotes: 0

Related Questions