Order Calculations

Nested linear loops

    int f1(int n) {
	int c = 0;
	for (int i = 0; i < n; i++)
	    for (int j = 0; j < i; j++)
		c++;
	return c;
    }

• Outer loop: O(n)
• Inner loop: O(i) = O(n/2) = O(n)
• Combined: O(n²)

Linear surrounding log

    int f2(int n) {
	int c = 0;
	for (int i = 0; i < n; i++)
	    for (int step = i; step > 0; step /= 3)
		c++;
	return c;
    }

• Outer loop: O(n)
• Inner loop: O(log_₃(n/2)) = O(log(n))
• Combined: O(n⋅log(n))

Log surrounding linear

    int f3(int n) {
	int c = 0;
	for (int step = n; step > 0; step /= 3)
	    for (int i = 0; i < step; i++)
		c++;
	return c;
    }

• Outer loop: O(log(n))
• Inner loop: O(step) = ???
• Combined: O(1n + ⅓n + ⅑n + …) = O(1.5n) = O(n)

Test question

    int f4(int n) {
	int c = 0;
	for (int j = 0; j < n; j++) {
	    for (int step = n; step > 0; step /= 3)
		for (int i = 0; i < step; i++)
		    c++;
	    for (int k = 0; k < 100; k++)
		c++;
	}
	return c;
    }

• First loop: O(n)
• Second & third loops combined: O(n)
• Fourth loop: O(1)
• All: O(n²)