Algorithms Question : Please explain me (with some examples) the best way to fin

Question

Algorithms Question: Please explain me (with some examples) the best way to find out big O (order of growth) from any number of given programming loops. Basically I need to have a better understanding of how i would figure out from any number of nested loops whether the big O is nLogn or LogN or N cube...etc. I've basic understanding of simple "for..loop" that has Big O of N or N square, but i'm struggling to find out big O of Logarithm and also, in some cases even though there are couple of inner/outer loops, still big O can be N only. Please explain me with different examples so that i would be able to figure out Big O from any number of nested loops(inner/outer) under any conditions.below are the couple of example code:

1)

int sum = 0;

for (int i = 1 i < N; i *= 2)

     for (int j = 0; j < i; j++)

          sum++;

2)

int sum = 0;

for (int i = 1 i < N; i *= 2)

for (int j = 0; j < N; j++)

      sum++;

Note: no copy/paste from Google search please.

Explanation / Answer

A nested loop is a loop within a loop, an inner loop within the body of an outer one. How this works is that the first pass of the outer loop triggers the inner loop, which executes to completion. Then the second pass of the outer loop triggers the inner loop again. This repeats until the outer loop finishes. Of course, a break within either the inner or outer loop would interrupt this process.

Output:

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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