I request everyone to help beginners to understand 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. asked 18 Aug '17, 08:06

Answer is hidden as author is suspended. Click here to view.
answered 18 Aug '17, 09:01

(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! answered 18 Aug '17, 12:50

It is a rough idea on how "Time taken by program to execute" increases with input data.
You can roughly approximate it as highest growing function in the expression. Eg, consider 2 loops
Its clear that in above, for first iteration of outer loop, inner loop executes N times, then N1, then N2...upto 0. Total operations = N+(N1)+(N2)...+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.
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.
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. answered 18 Aug '17, 13:34

Answer is hidden as author is suspended. Click here to view.
answered 18 Aug '17, 09:09
