Time Complexity for beginners

general
,
1

I request everyone to help beginners to understand time complexity.

  1. What is time complexity?
  2. How to calculate it?
  3. What is the benefit of knowing and calculating time complexity?
  4. What is worst case scenario, best case scenario and average case scenario in time complexity?

There are many beginner coders who are not that great with maths so I request everyone to keep it as simple as possible and please contribute to it. Please refer to links or explain in a way that doesn’t make it more complex, thank you.

1 Like
2

since you are a beginner more you do, more you will learn about it.
talking about benefits http://callmenick.com/post/time-complexity-analysis-why-its-important read this .

2 Likes
3

please upvote, less karma :frowning:

1 Like
4

(Consider a hypothetical case)

Time Complexity - Think of a dictionary that contains N (very large) name and now you need to find your name,

The most brute force solution you’ll think of is doing is a linear Search, Since there are N names so your time complexity is O(N) where O stands for ‘Big O notation’. For time being assume the Big O notation is something through which we denote time complexity and the value inside is the number of times the program runs.

The second solution you’ll think of is doing a binary search in dictionary to find your name, now you know that binary search uses divide and conquer technique through which we can find the solution in log(N) iterations. So time complexity is O(log(N))

The third solution you can think using a hashmap which in general take constant time to find a key. So for constant iterations, O(1).

Now you know three solutions to solve a single problem but for each solution we have different time complexity, here comes the use of time complexity. From above discussion we came to know that third solution is the best solution.

For a better explanation, follow this playlist from mycodeschool.

Hope this helps!

2 Likes
5

What is time complexity?

It is a rough idea on how “Time taken by program to execute” increases with input data.

How to calculate it?

You can roughly approximate it as highest growing function in the expression.

Eg, consider 2 loops-

for(i=0;i<n;i++)
   for(j=i;j<n;j++)

Its clear that in above, for first iteration of outer loop, inner loop executes N times, then N-1, then N-2…upto 0.

Total operations = N+(N-1)+(N-2)…+0 = N*(N+1)/2 = 0.5 x (N^2)+ 0.5 x N. The highest growing function here is N^2, so we call it O(N^2).

Similarly, if after analyzing your code you get function F= 2^n +N* N, then the time complexity is O(2^N). The lower powers are considered negligible compared to highest power, especially when N gets large.

What is the benefit of knowing and calculating time complexity?

You can find out before hand if your will get TLE or not. Judge machine can perform ~5 x 10^7 instructions per second (vary from site to site). If your complexity is O(N^2), and N can be upto 10^5, then it means that your code needs ATLEAST (10^5)^2 = 10^10 operations to give output. Divide by number of iterations per second, we see your code needs hunders or thousands of seconds to run, hence its too slow.

What is worst case scenario, best case scenario and average case scenario in time complexity?

Worst case scenario means, the type of test case where your code needs most time to run. Eg, take example of finding element X in array. If we find it in array, we break out of it and print “Found”. But what if X is last element, or not present at all? We will have to look through entire array in this case. This is worst case for our code, as we have to travel ENTIRE array. Similarly, X being somewhere in start is best case, as we are able to break earlier and save operations if X is found in start.

Average is pretty much, the average time taken.

1 Like
6

Thank you for explaining it.

1 Like
7

Thank you, it really helps.

8

Thank you, these links were helpful.