CODEWITHSUNDEEP
algorithmbig-o
CD'A
CD'A

Reputation: 41

How to find the big theta?

Here's some code segment I'm trying to find the big-theta for:

i = 1 
while i ≤ n do          #loops Θ(n) times   
   A[i] = i             
   i = i + 1 
for j ← 1 to n do       #loops Θ(n) times
   i = j 
   while i ≤ n do       #loops n times at worst when j = 1, 1 times at best given j = n.
     A[i] = i 
     i = i + j

So given the inner while loop will be a summation of 1 to n, the big theta is Θ(n2. So does that mean the big theta is Θ(n2) for the entire code?

The first while loop and the inner while loop should be equal to Θ(n) + Θ(n2) which should just equal Θ(n2).

Thanks!

Upvotes: 1

Views: 374

Answers (1)

dxiv
dxiv

Reputation: 17638

for j = 1 to n step 1
  for i = j to n step j
    # constant time op

The double loop is O(n⋅log(n)) because the number of iterations in the inner loop falls inversely to j. Counting the total number of iterations gives:

floor(n/1) + floor(n/2) + ... + floor(n/n)  <=  n⋅(1/1 + 1/2 + ... + 1/n)  ∼  n⋅log(n)

The partial sums of the harmonic series have logarithmic behavior asymptotically, so the above shows that the double loop is O(n⋅log(n)). That can be strengthened to Θ(n⋅log(n)) with a math argument involving the Dirichlet Divisor Problem.

[ EDIT ] For an alternative derivation of the lower bound that establishes the Θ(n⋅log(n)) asymptote, it is enough to use the < part of the x - 1 < floor(x) <= x inequality, avoiding the more elaborate math (linked above) that gives the exact expression.

floor(n/1) + floor(n/2) + ... + floor(n/n)  >  (n/1 - 1) + (n/2 - 1) + ... + (n/n - 1)
                                            =  n⋅(1/1 + 1/2 + ... + 1/n) - n
                                            ∼  n⋅log(n) - n
                                            ∼  n⋅log(n)

Upvotes: 1

Related Questions