How to evaluate the complexity of an algorithm?

Question

Python

Hello!
I solved the problem with https://www.hackerrank.com/challenges/climbing-the...
In short: there is a tournament table (scores), where players with the same points have the same place in the table and the list of points for the player (alice) after each games. At the exit, you need to return the metro in the standings after each game.
It immediately seemed like an obvious solution.

def climbingLeaderboard(scores, alice):
    return [sorted(set(scores + [ball]), reverse=True).index(ball) + 1 for ball in alice]

But such an algorithm turned out to be not optimal, since some tests fell on timeout. I estimated the complexity as O(len(scores) * len(alice)) The
following solution turned out to be correct:

def climbingLeaderboard(scores, alice):
    res = []
    scores = sorted(set(scores), reverse=True)
    i = len(scores)
    for b in alice:
        while (i > 0) and (b >= scores[i-1]):
            i -= 1
        res.append(i + 1)
    return res

How to calculate the complexity of the algorithm in this case? scores and alice are lists of different lengths scores > alice.
I would also like to know your opinion on this issue: such a skill as finding the optimal algorithm can be trained by constantly solving such problems? The fact is that having met such a problem in real life, I would never have thought to write something other than solution 1, and at the moment, it seems to me that solving a large number of such problems would not change this.

Answer 1

The skill of finding the optimal algorithm can be trained by solving any problems under conditions of limited resources. Say, for time optimization, your problem can be solved by compiling another array, where the index is the number of points, and the element content is the position in the table. Then the problem will be solved in linear time O(n) due to the increase in memory consumption.
I will give an example in pseudocode.

positions := array[0..max_scores] of 0
foreach of scores as score
  positions[score] := 1
position := 1
for i := max_scores to 0
  temp := position + positions[i]
  positions[i] := position
  position := temp
result := array[]
foreach of alice as score
  result[] := positions[score]

Answer 2

Because there are two nested loops, the complexity is O(n^2).
In the first case, it's even worse, we have three nested loops - O(n^3). Learn what Big O notation means and how to evaluate algorithms with it.
To be clear, when evaluating with large O, we do not operate on specific values ​​like len(alice). We are interested in the worst option, so everything insignificant is discarded. The most expensive part is the cycles.
Examples:
One loop - O(n)
Two non-nested loops - still O(n)
Two nested loops - already O(n^2), etc.