CODEWITHSUNDEEP
pythonalgorithm
user1050619
user1050619

Reputation: 20856

Big o value of sample program

Im trying to big o worst case scenario for a programming logic and need some clarification.

Here is a very simple program, it takes a number - 2938023 and each char is multiplied by a random number and populated in a list.

Once the list is populated, I get the max value as my result. 

from random import randint
def test(A):
    result = []
    for each in str(A):
        result.append(int(each)*randint(0,9))   
    return max(result)


print test(2938023)

What is the big o worst case of this operation? As the list - str(A) is iterated only once, should I consider it to be log(n) or

Should I consider it n*n as the list is again iterated to get the max value. There is 2 pass on the list based on n.

Upvotes: 0

Views: 61

Answers (1)

Darkstarone
Darkstarone

Reputation: 4730

Ok so the comments have given a pretty clear answer - but just to clarify (and also properly answer the question):

The two operations that define the big-O here is:

  • for each in str(A): - This is an O(n) operation, it looks at each character in the string (A).
  • max(result) - This is also an O(n), as we have to iterate the entire list to fix the maximum (result).

Since len(A) == len(result) we can call this 2n (as opposed to nm), and since it's big-O, we drop the constant factor, resulting in: O(n).

If you wanted to remove the constant factor entirely you could rewrite the function as:

from random import randint
def test(A):
    max_item = 0
    for each in str(A):
        new_item = int(each)*randint(0,9)
        if new_item > max_item:
            max_item = new_item  
    return max_item

Which is also O(n), but only iterates the string.

Upvotes: 1

Related Questions