for (int i = 0; i < n; i++)
{
for (int k = 1; k < n; k*=2)
{
System.out.println("Hello!");
{
}
So my question is- what's the wrst case analysis, and why? Very brief is fine. I'm taking the class online and have just been crazy busy. Any help is appreciated!
for (int i = 0; i < n; i++)
{
for (int k = 1; k < n; k*=2)
{
System.out.println("Hello!");
{
}
So my question is- what's the wrst case analysis, and why? Very brief is fine. I'm taking the class online and have just been crazy busy. Any help is appreciated!
Correct me if I'm wrong but a for loop is O(N). So this nested for loop is (N^2). Big O for outer is O(N). Big O for inner is O(2N). So O(N * 2N) = O(N^2) dropping the constant.
For #2:
Outer loop is again O(N). inner loop is now O((N-1) / 2), or O(N/2). so O(N * (N/2)) is again O(N^2) because you get rid of the constant.
Again, its been a while since I've done these, but I think that is correct...
Thanks a bunch guys- I got the first one without an issue, but made the same mistake wheels did for the 2nd fragment. Since the class is just starting, it's fairly easy to try and teach myself a little on the side..thanks again!