Recently started with this so need your help, Lets say you have nested for loops as shown below, both ranging from 1 to n, how does one calculate the running time for the same in terms of Big O, Theta, Omega?
for(i=1; i<n; i++) {
for(j=1; j<n; j++) {
//some piece of code
}
}
for(i=1; i<n; i++) {
for(j=1; j<n; j++) {
//some piece of code
}
}
So let's look closer at this piece of code. Say we have a set of 10 items (n) and we execute these loops one by one. First it has to pass the i loop. he'll pas it for 1, then that 1 goes into the second loop 10 times before 1 becomes 2. In total it has to pass loop 100 times before reaching the end. In big O notation, we always calculate O for the worst case scenario. That is, needing an item that is at the end of your loop. Say we add 1 to n. How many times it has to pass the loop now? 11 * 11 and that is 121. So whenever your input grows 1, the cost of this algorithm grows exponentially. That is why we say O(n^2).