I had this question for my assignment the other day, but I was still unsure if I'm right.
for(int i =1; i <n; i++) //n is some size
{
for(j=1; j<i; j++)
{
int k=1;
while (k<n)
{
k=k+C; //where C is a constant and >=2
}
}
}
I know the nested for loops is O(n^2) but I wasn't sure with the while loop. I assumed that the whole code will be O(n^3).
int k=1;
while (k<n){
k=k+C //where C is a constant and >=2
}
This will take (n-1)/C steps: write u = (k-1)/C. Then, k = Cu + 1 and the statement becomes
u=0;
while(u < (n-1)/C) {
u=u+1
}
Hence the while loop is O(n) (since C is constant)
EDIT: let me try to explain it the other way around.
Start with a dummy variable u. The loop
u=0;
while(u < MAX) {
u = u+1
}
runs MAX times.
When you let MAX = (n-1) / C, the loop is
u=0;
while(u < (n-1)/C) {
u=u+1
}
And that runs (n-1)/C times.
Now, the check u < (n-1)/C is equivalent to C*u < n-1 or C*u + 1 < n, so the loop is equivalent to
u=0;
while(C*u + 1 < n) {
u=u+1
}
Now, suppose that we rewrote this loop in terms of a variable k = C * u + 1. Then,
u=0;
k=1; // C * 0 + 1 = 1
The loop looks like
while(C*u + 1 < n) {
while(k < n) {
and the inner condition is
u=u+1
k=k+C //C * (u+1) + 1 = C * u + 1 + C = old_k + C
Putting it all together:
int k=1;
while (k<n){
k=k+C
}
takes (n-1)/C steps.
The inner loop is literally O(n/C)=O(n), so yes, overall it's O(n^3) (the second loop has an upper bound of O(n))
Formally, you may proceed using the following methodology (Sigma Notation):
Where a symbolizes the number of constant operations inside the innermost loop (a = 1 if you want to count the exact number of iterations).
Well, you would need to look at how many times the while loop body is run for a given value of n and C. For example n is 10 and C is 3. The body would run 3 times: k = 1, k = 4, k = 7. For n = 100 and C = 2, the body would run 50 times: k = 1,3,5,7,9,...,91,93,95,97,99. It is a matter of counting by C until n. You should be able to calculate the Big-O complexity from that clue.
