Member Avatar for needhelp83

Alright, I didn't get this one quite right on the homework, but I am trying to figure out exactly how to solve this thing. The answer was n log n , but how do you total this up when going through the loop

i = n                                                                       1
   while i >= 1                                                         n
       j =  i        1
         while j <= n                                                   n?
              <body of the j loop>, needs  Theta(1)      \\Theta (1) 
              j = j*2                                                      1
         end j while 
     i =i-1                                                                  1
end i while

Now when I total up I disregard so I left with n. Now I assume that the inner loop is log n, but I don't fully understand. Thanks for any help.

  • 3 Contributors
  • 2 Replies
  • 73 Views
  • 1 Month Discussion Span
  • Latest Post Latest Post by فلذمنصور
Member Avatar for Rashakil Fol

How many steps does it take for i*2^k to be greater than n?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.