You are not logged in. Please login at www.codechef.com to post your questions!

×

Time Complexity for beginners

1
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.

asked 18 Aug, 08:06

monsterguy's gravatar image

2★monsterguy
695
accept rate: 0%


Answer is hidden as author is suspended. Click here to view.

answered 18 Aug, 09:01

raj79's gravatar image

4★raj79
(suspended)
accept rate: 11%

Thank you, these links were helpful.

(19 Aug, 09:25) monsterguy2★

(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!

link

answered 18 Aug, 12:50

sandeep_007's gravatar image

4★sandeep_007
7677
accept rate: 13%

Thank you, it really helps.

(18 Aug, 14:10) monsterguy2★
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.

link

answered 18 Aug, 13:34

vijju123's gravatar image

4★vijju123 ♦
11.3k1316
accept rate: 18%

1

Thank you for explaining it.

(18 Aug, 14:09) monsterguy2★
Answer is hidden as author is suspended. Click here to view.

answered 18 Aug, 09:09

twinklebajaj's gravatar image

3★twinklebajaj
(suspended)
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×214
×19

question asked: 18 Aug, 08:06

question was seen: 208 times

last updated: 19 Aug, 09:25