Time Complexity - Calculating Worst Case For Algorithms

Question

I am reading some information on time complexity and I'm quite confused as to how the following time complexities are achieved and if there is a particular set of rules or methods for working this out?

1)

Input: int n
for(int i = 0; i < n; i++){
 print("Hello World, ");
}
for(int j = n; j > 0; j--){
 print("Hello World");
}

• Tight: 6n + 5
• Big O: O(n)

2)

Input: l = array of comparable items
Output: l = array of sorted items
Sort:
for(int i = 0; i < l.length; i++){
 for(int j = 0; j < l.length; j++){
 if(l{i} > l{j}){
} }
 Swap(l{i},l{j});
}
return ls;

• Worst Case Time Complexity: 4n2 +3n+2 = O(n2)

Answer 1

For a given algorithm, time complexity or Big O is a way to provide some fair enough estimation of "total elementary operations performed by the algorithm" in relationship with the given input size n.

Type-1

Lets say you have an algo like this:

a=n+1;
b=a*n;

there are 2 elementary operations in the above code, no matter how big your n is, for the above code a computer will always perform 2 operations, as the algo does not depend on the size of the input, so the Big-O of the above code is O(1).

Type-2

For this code:

for(int i = 0; i < n; i++){
 a=a+i;
}

I hope you understand the Big-O in O(n), as elementary operation count directly depend on the size of n

Type-3

Now what about this code:

//Loop-1
for(int i = 0; i < n; i++){
 print("Hello World, ");
}
//Loop-2
for(int i = 0; i < n; i++){
 for(int j = 0; j < n; j++) {
 x=x+j;
 }
}

As you can see loop-1 is O(n) and loop-2 is O(n^2). So it feel like total complexity should be O(n)+O(n^2). But no, the time complexity of the above code is O(n^2). Why? Because we are trying to know the fair enough count of elementary operations performed by the algorithm for a given input size n, which will be comparatively easy to understand by another person. With this logic, O(n)+O(n^2) become O(n^2), or O(n^2)+O(n^3)+O(n^4) become O(n^4)!

Again, you may ask: But how? How all the lower power of Big-O become so insignificant as we add it with a higher power of Big-O, that we can completely omit them (lower powers) when we are describing the complexity of our algorithm to another human?

I will try show the reason for this case: O(n)+O(n^2)=O(n^2).

Lets say n=1000 then the exact count for O(n) is 1000 operations and the exact count for O(n^2) is 1000*1000=1000000, so O(n^2) is 1000 time bigger than O(n), which means your program will spend most of the execution time in O(n^2) and thus it is not worth to mention that your algorithm also has some O(n).

PS. Pardon my English :)

• Varun Chandran: nice explanation

Answer 2

In the first example, the array has n elements, and you go through these elements Twice. The first time you start from index 0 until i, and the second time you start from index n to 0. So, to simplify this, we can say that it took you 2n. When dealing with Big O notation, you should keep in mind that we care about the bounds:

As a result, O(2n)=O(n) and O(an+b)=O(n)

Input: int n // operation 1
 for(int i = 0; i < n; i++){ // operation 2
 print("Hello World, "); // Operation 3 
 }
for(int j = n; j > 0; j--) // Operation 4
 {
 print("Hello World"); //Operation 5
 } 

As you can see, we have a total of 5 operations outside the loops.

Inside the first loop, we do three internal operations: checking if i is less than n, printing "Hello World", and incrementing i .

Inside the second loop, we also have three internal operations.

So, the total number of of opetations that we need is: 3n ( for first loop) + 3n ( second loop) + 5 ( operations outside the loop). As a result, the total number of steps required is 6n+5 ( that is your tight bound).

As I mentioned before, O( an +b )= n because once an algorithm is linear, a and b do not have a great impact when n is very large.

So, your time complexity will become : O(6n+5) =O(n).

You can use the same logic for the second example keeping in mind that two nested loops take n2 instead of n.

• mino: wait, isn't print("Hello World"); OUTSIDE the loop?
• John: No, it is INSIDE the loop as shown in your code ( Sorry, I accidently added a '{' ). I have just fixed it.
• mino: If it is inside then why is it included in the calculations for being OUTSIDE i.e.: Operation 3.

Answer 3

I will slightly modify Johns answer. Defining n is one constant operation, defining integer i and assigning it to 0 is 2 constant operations. defining integer j and assigning with n is another 2 constant operations. checking the conditions for i,j inside for loop,increment,print statement depends on n so the total will be 3n+3n+5 which is equal to 6n+5. Here we cannot skip any of the statements during execution so its average case running time will also be its worst case running time which is O(n)