0

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)
Improve this question

3 Answers 3

Reset to default
6

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 :)

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

nice explanation
5

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 n² instead of n.

Improve this answer

3 Comments

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

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)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.