python 3.x - Python3.x - counting occurences of all substrings using dictionaries -

given string s, code count number of occurrences of possible substrings of string s.

#count[i]=no of different substrings in string occurs times count=[0]*(100001) a=input() dic={} n=len(a) in range(n):     temp=""     j in range(i,n,1):         temp+=a[j]         if temp in dic:             dic[temp]+=1         else:             dic[temp]=1 k,v in dic.items():     count[v]+=1 

for example, string "ababa", array be:

• cnt[1]=4 {"ababa", "abab", "baba", "bab"} occur once
• cnt[2]=4 {"aba", "ab", "ba", "b"} occur twice
• cnt[3]=1 {"a"} occur thrice
• cnt[4]=0
• cnt[5]=0

i interested in knowing runtime of code

there 2 parts of code consider separately:

1. the nested loop build `dic`.
2. the loop build `count`.

for 1. there 2 loops consider. loop run n times , j loop run n-i times each time.

this means j loop run n times first time, n-1 times second time , on till runs once when i = n-1. total running time of block n(n+1)/2, o(n^2).

(note: assuming dictionary access take constant time case of time).

for 2. there 1 loop consider run many times unique substrings exist. string of length n, maximum number of unique substrings again n(n+1)/2, o(n^2).

so, running time o(n^2). n = 10e5, number of operations ~10e10, take around 10 seconds, using standard assumption 10e9 operations take 1 second.