CODEWITHSUNDEEP
algorithmbig-onotation
hollyjolly
hollyjolly

Reputation: 1

Solving Running time Big Theta Notation

Consider finding the total running time as function of n in these two loops:

(1)

q  <- 1
while q <= n
     p  <- 1
          while p <= q 
           p <- p + 1
     q  <-  2 * q 

(2)
q,s <- 1, 1
while s < n
    for j <- 1 to s        
          k  <- 1
          while k < = j  
                 k  <- 2 * k        
     q  <- q + 1
     s  <- q * q

Going off of what I know I believe: (1) is theta(n * lg(n)) where n represents time for inner loop, and lg(n) for the outer loop. (2) is theta(n * lg(n) * sqrt(n)) where n represents time for the for loop, sqrt(n) for the outer loop, and lg(n) for the inner while loop.

I am not sure if this is correct. Any advice would be appreciated.

Upvotes: 0

Views: 533

Answers (1)

0Interest
0Interest

Reputation: 1842

(1):

This is not the correct way to view this, in fact, the inner while-loop does not do "n cycles lg n times", it does q cycles whatever this number may be each iteration!

The correct way to analyze this is saying that the inner while-loop runs q times, and q takes the numbers 1, 2, 4, ... , n (Yes, the out while-loop runs Θ(lg n) times).

Thus the whole running times is:

1 + 2 + 4 + ... + L beware that if n is not a perfect power of 2, it goes up to the largest power less than n. Thus we can say it runs until it hits n (L = Θ(n))

Computing this gives us a geometric progression with lg(n) elements:

1 + 2 + 4 + ... + n = Θ(n)

(2):

Not a final solution, but a hint/kickstart Your analysis is still wrong by saying the for-loop runs ~n times, this loop simply runs s times, and s is changing with each and every iteration. On iteration t we have s = t^2.

The analysis goes as so: The for-loop and its inneer while-loop are correlated, j runs from 1-s and the while loop runs lg(j) - they are correlated because j is changed in each of every iteration of the for-loop. But we need to keep in mind that s is changing as-well, and so the for-loop runs s ∈ {1, 4, 9, ..., n}

Upvotes: 0

Related Questions