1

I have a question regarding time complexity in my codes. I tried to refer to a number of sites and tutorials and also stackoverflow explanations but still could not understand how we calculate or determine the time complexity of codes. If possible, is it ok to check my codes and explain based on it and also provide some EASY examples or links (Im still learning) to study it.

I tried this code and try to submit it but the time complexity is high so it is not accepted. Is there a way to reduce the time complexity too?

question is from this link

def large_element(array):
    stack = []
    took = False
    for i in range(len(array)):
        s_integer = array[i+1:]
        if i != len(array)-1:
            for ii in range(len(s_integer)):
                if array[i] < s_integer[ii] and took == False:
                        stack.append(s_integer[ii])
                        took = True
                elif array[i] > s_integer[ii] and took == False and ii == len(s_integer)-1:
                        stack.append(-1)
                        took = True
            took = False
        else:
                stack.append(-1)
    return stack

import time
start_time = time.time()
integer = [4,3,2,1]
print(large_element(integer))

My current understanding is that my code have 2 times for loop to loop each element so this will be O(n2)?

By the way, the output is: [-1, -1, -1, -1]

AcaNg
  • 704
  • 1
  • 9
  • 26
Anonymous
  • 477
  • 3
  • 12
  • 1
    the most simple (but sometimes inaccurate) way to measure time complexity is to count how many times you do iteration. – AcaNg Aug 01 '19 at 01:55
  • Yes, I read about that too but unfortunately some cases are different. In my case, does it mean that it has O(n*n)? I still dont fully understand it yet and wanted to learn. – Anonymous Aug 01 '19 at 01:58
  • I still dont understand. Could you show some detailed examples based on my codes please? – Anonymous Aug 01 '19 at 02:16
  • it's a part of [bigO](https://en.wikipedia.org/wiki/Big_O_notation). some explanation of time complexity: [1](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) [2](https://stackoverflow.com/questions/107165/big-o-for-eight-year-olds) [3](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it?rq=1). I'm not an expert in this field so I can't evaluate your code properly, maybe someone will come with a graph. – AcaNg Aug 01 '19 at 02:27

1 Answers1

3

A simplified yet powerful way of doing this is giving each line of code a cost and count how many times this line is run. Of course, you should keep your lines of code simple for this to make sense.

The cost of a line does not need to be precise, as constants are ignored in Big O notation.

Simple example: n equals the size of the list x

def print_list(x : list):
    for i in x:          # cost = c1; count = n
        print(i)         # cost = c2; count = n
    print('done')    # cost = c3; count = 1

The line with the for is called n times because although the for is executed only once, the comparison to decide if the loop should continue is made n times.

The time complexity of this function is equal to the sum of the products of the cost of each line and the amount of times it is repeated:

complexity = c1×n + c2×n + c3×1 = O(n)

In this case, the costs are ignored because they happened to be constants. However, the cost of an instruction can be dependent of the size of the input, most of times when the instructions calls a subroutine.

Also, in the example I gave, each instruction was at most called n times, but in places like nested loops this count may be n², log(n), etc.

I would recommend reading the book Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. This explanation is mostly based on what the books says in the first chapters.

Heladio Amaya
  • 968
  • 10
  • 20