I understand basic time complexity, but I struggle to know when the time complexity is correlated with log. Here's my solution from the HackerRank Ice Cream Parlor question: https://www.hackerrank.com/challenges/icecream-parlor/problem

def icecreamParlor(m, arr):

    for i in range(len(arr)):
        for k in range(i 1, len(arr), 1):
        
            if arr[i]   arr[k] == m:
                return [i 1, k 1]

It's my understanding that the nested loops would normally be O(n^2); however, does that change since I'm not looping through the entire list every time on the second loop? As I'm starting from i on the inner loop, the time spent looping through it increasingly decreases. What would be the time complexity of this?

CodePudding user response：

At the top level, you're looping N times. For each i of those loops, you're looping some M = N-i times. Notice that this means that M averages to half of N: (5 4 3 2 1 0) == (5 5 5 5 5)/2. So the overall time complexity is O(N * N/2), which is equivalent to O(N*N) or O(N**2).

CodePudding user response：

This is still O(n^2). Your outer loop is doing N work while your inner loop is doing n-1 work.

If you were to write out the i and k counts per loop, you would get something like this for len(arr) = 5

i = 1 k = 2,3,4,5
i = 2 k = 3,4,5
i = 3 k = 4,5
i = 4 k = 5
i = 5

This pattern of for loops resembles a Triangular number (https://en.wikipedia.org/wiki/Triangular_number). From the article the way to find the triangle number for any given N is N 1 choose 2. This gives us the formula N(N 1)/2. Asymptotically this function gives us O(n^2) behavior

CodePudding user response：

It's still O(n^2) - it's obviously gonna be faster than 2 nested loops that have n iterations each but you still have 2 loops that are variable-dependent. If you have any more questions lmk :)

CodePudding user response：

I recommend using Big-O python lib! You just need to import it and you can run your code inside it :) This will help you in several projects. Keep up the grind!