Please explain the following question to me in detail, explaining how you derive
ID: 3620379 • Letter: P
Question
Please explain the following question to me in detail, explaining how you derived everything if possible:for (i = 0; i < n; i++)
for (j = i; j <= n; j++)
sum++;
For this code fragment, please determine a function such that t: N -> N and T(n) is the number of times sum++ is executed. Also state the big O and Big Omegas (consisting of Omega(n), Omega(n2), Omega n(log(n)). For this, my attempt at the problem yielded O(n(logn) and the equation being c (c is a constant) x n(log(n)). My reasoning behind the equation was that the outer loop iterates n amount of times while the inner loop iterates less as the outer loop increases. Therefore, the inner loop iterates less as the outer loop goes through iterations. My main problem is with the Big Omegas though. I have no clue how to determine them nor am I sure if a code fragment can have more than one Big Omega. I was under the impression that there can be multiple big Omega's. For this code fragment, please determine a function such that t: N -> N and T(n) is the number of times sum++ is executed. Also state the big O and Big Omegas (consisting of Omega(n), Omega(n2), Omega n(log(n)). For this, my attempt at the problem yielded O(n(logn) and the equation being c (c is a constant) x n(log(n)). My reasoning behind the equation was that the outer loop iterates n amount of times while the inner loop iterates less as the outer loop increases. Therefore, the inner loop iterates less as the outer loop goes through iterations. My main problem is with the Big Omegas though. I have no clue how to determine them nor am I sure if a code fragment can have more than one Big Omega. I was under the impression that there can be multiple big Omega's.