[JAVA] Study Guide Problems 5. What is the asymptotic complexity of the followin

Question

[JAVA] Study Guide Problems

5. What is the asymptotic complexity of the following methods or code segments, in terms of the Big-O notation?

a) void methodA(int n)
{
for (int i=n; i>1; i-=2)
{
System.out.println(i);
}
}

b) void methodB(int n)
{
for (int i=n; i<=n; i++)
{
for (int j=n; j>1; j=j/2)
{
System.out.println(j);
}
}
}

c) Code segment:

int sum = 0;
int X = 100000;
for (int i = 1; i <=4 * N; i++)
{
for (int j = 1; j <= X + 2; j++)
{
sum++
}
for (int j = 1; j <= X * 100; j+= 2)
{
for (int k = 1; k <= X * X; k++)
{
sum++;
}
}
sum++;
}
System.out.println(sum);

d) Code segment:

int sum = 0;
int X = 100000;
for (int j = 0; i < 100 * N; j++)
{
for (int i = N; i > 0; i /= 2)
{
sum++
}
}
System.out.println(sum);

Link to Source PDF:

https://www.dropbox.com/s/1lrjfjs38plzska/Practice_Final_Exam.pdf?dl=0

Explanation / Answer

a) void methodA(int n)
{
for (int i=n; i>1; i-=2)
{
System.out.println(i);
}
}

FOR loop runs (n-1) times : for i = n to i=2

So, Big-O = O(n)

b) void methodB(int n)
{
for (int i=n; i<=n; i++)
{
for (int j=n; j>1; j=j/2)
{
System.out.println(j);
}
}
}

Here condition for outer FOR loop: i<=n and initial value of i = n
So, outer for loop runs 1 times only

Now , inner for loop runs: log(n) time, because in each iteration we are dividing j by 2

Big-O = O(logn)

c) Code segment:
int sum = 0;
int X = 100000;
for (int i = 1; i <=4 * N; i++) // This FOR loop runs: 4N times
{
for (int j = 1; j <= X + 2; j++)// for each value of i, it runs: 100002 times
{
sum++
}

for (int j = 1; j <= X * 100; j+= 2) //for each value of i, this FOR loop runs: 100000*100/2= 5000000 times
{
for (int k = 1; k <= X * X; k++) // This for loop runs : sqrt(100000) times
{
sum++;
}
}
sum++;
}
System.out.println(sum);

So T(n) = 4*N*100002 + 4*N*5000000*sqrt(100000)
       = 4*N(100002 + 5000000*sqrt(100000))

   So, ignoring all constants:
   Big-O = O(N)

d) Code segment:
int sum = 0;
int X = 100000;
for (int j = 0; i < 100 * N; j++) // this FOR loop runs: 100*N times
{
for (int i = N; i > 0; i /= 2) // THis FOR loop runs log(N) time (in each iteration we are dividing j by 2)
{
sum++
}
}
System.out.println(sum);

T(n) = 100*N*log(N)

   Big-O = O(NlogN)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.