Join 307,148 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 1,735 people online right now. Registration is fast and FREE... Join Now!
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
CODE
i = n 1 while i >= 1 n j = i 1 while j <= n log n? <body of the j loop>, \\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. Any help??
I don't think that completely writing out the solution, including all the mathematical lingo, will be of much help here, so I'll be brief. Yes, the first while loop is O(n) because it iterates n times. In the inner loop, j gets multiplied by 2 until it becomes greater than n. The initial value of j iterates from 1 to n. So it will have to be multiplied at least once, and at most log n times. When it equals to n, it will be multiplied once. when it equals to 1 it will be multiplied log n times. Therefore the inner loop is O(log n).
I don't think that completely writing out the solution, including all the mathematical lingo, will be of much help here, so I'll be brief. Yes, the first while loop is O(n) because it iterates n times. In the inner loop, j gets multiplied by 2 until it becomes greater than n. The initial value of j iterates from 1 to n. So it will have to be multiplied at least once, and at most log n times. When it equals to n, it will be multiplied once. when it equals to 1 it will be multiplied log n times. Therefore the inner loop is O(log n).
Awesome, now with that said I am assuming you multiply the outer loop by the inner loop to give me n log n and I just drop the 1's?
Awesome, now with that said I am assuming you multiply the outer loop by the inner loop to give me n log n
No, I'd have to use some math to explain exactly what happened - it involves a ceiling function (http://en.wikipedia.org/wiki/Floor_and_ceiling_functions) and a simple inequality. You can think that that's what I did for now, but be aware that it's not how it was calculated.
QUOTE
and I just drop the 1's?
No, some of those 1's stay - they are your basic operations, and you have to calculate how fast those 1's will grow as n grows. That's the first part of analyzing algorithms - determining the basic operation. The other 1's, like those outside your loops, may be ignored - they don't contribute much of anything.
Well, those constants could be dropped after you're done all the calculations, in order to make the Big-O look "simpler". But while calculating the Big-O, what is usually being done is increasing the amount operations being performed, because that's the nature of Big-O. So,
n+1 < n + n = 2n (for n greater than 1) But such constants drop off at the end of the calculation, anyway. Most of the time, it's just a matter of formality. Let me add that parts of the answer with the lesser big-O can be dropped off too, so,
O(n logn + n) = O(n log n) + O(n) = O(n logn). In fact, that's what happened in this case. My final answer was,
1/2 * n * logn + n which can be considered as O(n logn).
No, it wasn't the case of a constant, that's why I said "too". I was simply making a general notion - no operations should be dropped off while calculating the Big-O.
Forum Index:
Programming Help |
C and C++ |
VB6 |
Java |
VB.NET |
C# |
ASP.NET |
PHP |
ColdFusion |
Perl and Python |
Ruby |
Databases |
Other Languages |
Game Programming |
Mobile Development |
Software Development |
Computer Science |
Industry News |
Programming Tutorials |
C++ Tutorials |
Visual Basic Tutorials |
Java Tutorials |
VB.NET Tutorials |
C# Tutorials |
Linux Tutorials |
PHP Tutorials |
ColdFusion Tutorials |
Windows Tutorials |
HTML/JavaScript Tutorials |
CSS Tutorials |
Flash Tutorials |
Web Promotion Tutorials |
Graphic Design & Photoshop Tutorials |
Software Development Tutorials |
Database Tutorials |
Other Language Tutorials |
ASP.NET Tutorials |
Game Programming Tutorials |
WPF & Silverlight Tutorials |
| 
