Python - Complexity of O(n^2) number of jumps in list

Question

If a list has 3 elements, how is that O(n^2) means we have to do 9 jumps to navigate a collection of 3 elements? If a jump is just one element how can it be 9 jumps?

list = [1, 2, 3]

I don't understand what the author means we have to do 9 jumps.. Can someone explain?

I think it just a general saying, which means that O(n2) means to double the loop over list. For example when you want to look for duplicates in list for each element and you loop twice over the loop it is O(n2) complexity — Yossi Levi, Sep 30 '20 at 07:26
The complexity depends on the task you are trying to achieve, for some tasks you will have to loop over the list one time (then it is O(n)), for other two times (O(n^2)) etc... Look at solid.py's answer for examples! — A Co, Sep 30 '20 at 09:29
Does this answer your question? [What is a plain English explanation of "Big O" notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) — Tomerikoo, Sep 30 '20 at 09:45

score 3 · Answer 1 · answered Sep 30 '20 at 07:53

The code example provided below is O(n) because it uses a for loop to iterate over n elements.

n = len(list) # n = the length of the list here 3.
for i in range(0, n): # This runs n = 3 times, where n is the size of the list O(n)
    print(i)

Now consider a nested for loop, meaning a second loop within your current for loop. This is O(n^2) due to iterating over n*n elements.

n = len(list) # n = the length of the list here 3.
for i in range(0, n): # This runs n = 3 times.
   for j in range (0, n): # This runs n = 3 times for each value of the i.
       print(j)

Think of it this way, the above code segment prints 0, 1, 2 in the inner loop as many times as the outer loop specifies, in this case 3. Therefore at the end 0, 1, 2, 0, 1, 2, 0, 1, 2 will be printed which is exactly n*n = 3*3 = 9 elements.

score 1 · Answer 2 · answered Sep 30 '20 at 07:29

O(n^2) means that for you to reach the desired output of that input you have to go through all the input data twice, for example if your solution consists of a nested loop in which the outer and the inner loop both go from 0 to n (Size of the input data).

You can check this for more Big O notation coding examples.

score 0 · Answer 3 · answered Sep 30 '20 at 09:35

Big O notation gives us an estimate of the number of operations we have to perform in order to use the algorithm on N elements if Big O notation is n then we need to n operations to perform for the function. Linear search in list takes Big O of n Why

def linearsearch(numbers,s):
 for i in range(len(numbers)):
  if numbers[i] == s:
    return i
 return -1

We will look a worst case that s is not in the list. For that, we will do all constant operations n times if our list size is n. When n increase time will be increase linearly since the time taken for the linearsearch depends on size of the list

If all constant operations take c time then when we do for 5 elements it takes 5c and if we do for 10 elements it takes 10c (Here we assume the worst case when there is no s in the list)

Lets see O(n2)

If we have n elements then the time taken will be square of n

Lets look following linear search in 2D list


Numbers = [[1,2,3][4,5,6]]

def linearsearch(numbers,s):
 for inner in range(len(numbers)):
  for i in range(len(numbers[inner])):
   if numbers[inner][i] == s:
    return i
 return -1

With above code and we consider some assumptions to illustrate n2

Inner list has n elements and outer list also has n innerlist

When we need to search an element like s inside the innerlist then we need to do the thoee operations n2 times If we have 2 elements in the innerlist and 2 innerlist in the outer list Then 4 c will be average time if we consider c for time taken for constant operations 3,3 then 9 So if we have n elements inside the inner list then the tims complexity will be O(n2)

Python - Complexity of O(n^2) number of jumps in list

3 Answers3