shankysodhi's blog

Complexity of an algorithm
By shankysodhi, 14 years ago, In English

Hi Everyone.

I know i shouldn't have written a blog post for this . But since there is no other way . I am doing it here .

I am (like most/or at least some other people here) new to this fantastic world of problem/puzzle solving programming . And i face a very serious problem here.

Most of the time when i start solving a problem. I start coding .. submit it .. and then find out that my solution exceeds the time limit.

For example :

I was participating in the topcoder SRM 504.5 in div 2(obviously). And i was trying to solve the jackpot problem.

the problem statement is at :

http://www.topcoder.com/stat?c=problem_statement&pm=11432

Now during the course of 75 mins i was unable to solve even this basic(now i know) problem, spending all the time to find an effective and fast way to solve it. I was shocked to look at the possible solution . It was straightforward.

highlight to reveal :

while(jackpot>0)
{
sort(ALL(money));
money[0]++;
jackpot--;
}
sort(ALL(money));
return money;



Now most of the people here (red violet yellow and even others)  , i suppose, figure out whether their solution is gonna work or not before they even start coding . They (You - if you can do it too) can figure out the complexity of the problem and given the limits of the input are aware of the effectiveness of their solution.

I have been trying to learn complexity for quite some time. But still hasn't succeeded in it yet. So could please someone of you, take some time of their precious time to explain it in details (with examples) . Or if not could someone please refer blogs, posts or web links of something that can be useful .

I know their are a lot of people out there like me who face the same problem . It would be so grateful of you.

Thanks.

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
you just need more practice. on your 20th SRM you will solve it without problems :)
Recommend open arena, and start solve past problems - 1SRM/day - it really helped me when I started.

most easy way to count complexity is to count number of cycles will be executed - if around 1.000.000 - 70.000.000 it will definitely pass, if more than 200.000.000 not.    
try same code in practice arena, run with some data and check what time took to execute it.

to solve this problem you had to check upper bound for jackpot and calculate that O(N * log(N) * jackpot) cycles will work here. (I'd better try O(N * jackpot) )
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks a lot Oleg for you advice.

Well I am a novice here .... and as you would have expected ...i got some questions.

what time limit are you talking about when u say 200.000.000 is not enough? And moreover did you get this number by experience or is there a way to calculate it ... you know when there is lesser or more time limit given?

When you say O(N * log(N) * jackpot) .... is jackpot for the outer loop and n* log n for sorting the array ...???

And you said you would do it in N*jackpot . I may be wrong here . But is N there because you just need the min number in the array ( and dont need the whole array sorted ) ?? so just sweep through to get the min . Is that your approach ?

→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    shankysodhi>> what time limit are you talking about
    We are talking about TC's time limit, right :D

    shankysodhi>> And moreover did you get this number by experience or is there a way to calculate it
    Oleg>> try same code in practice arena, run with some data and check what time took to execute it.

    shankysodhi>> When you say O(N * log(N) * jackpot) .... is jackpot for the outer loop and n* log n for sorting the array ...??? .......... Is that your approach?

    You are right for both questions. You should try to verify your doubt instead of asking for answer immediately.

    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    TC's time limit is 2 sec. and memory limit is 64 MB :)
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In addition to what Oleg just said, I think you should code first the previous SRMs, TCOs and TCHSs, that are somewhat easier than today's and when you don't get how to do a problem, start thinking, take a piece of paper, start writing ideas that you think that can solve it and try to model it to your problem that eventually It'll come out something. If not, huge majority of topcoder's contests have editorials, that will give you tips to help this and future problems. Just practice, practice and practice :)
→ Reply