CODEWITHSUNDEEP
pythonperformancetime-complexitybig-o
Henry Gilbert
Henry Gilbert

Reputation: 95

What is the time complexity of this solution?

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?

Upvotes: 1

Views: 379

Answers (4)

peepdsus
peepdsus

Reputation: 36

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

Upvotes: 2

Kenéz Megyeri
Kenéz Megyeri

Reputation: 31

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!

Upvotes: 3

Lucretiel
Lucretiel

Reputation: 3324

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

Upvotes: 4

greenguy0120
greenguy0120

Reputation: 21

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 :)

Upvotes: 2

Related Questions