Space complexity

#1

how is the space complexity is 26^n?? the answer can ve greater then this…

#2

hello @shampblocks
yeah it will be slightly more.

see what we are storing for each node,its value and the address of node in its parent node.

let say pointer take 4bytes and value takes 1 bytes so total memory consumed by a value and address is 5bytes (say c).

now consider trie.
at level 1 . we will have 26 nodes so 26*c space.
at level 2 . we will have 26 * 26 node so 26 * 26 * c space.
at level 3 . we will have 26 * 26 * 26 node so 26 * 26 *26 * c space.
…
…
…
at level n we will have 26 ^ n nodes so 26 ^n *c space.

adding all spaces.
26 * c + 26 * 26 * c + 26 * 26 * 26 c + … + 26 ^ n * c
take c common
c ( 26 + 26^2+ 26^3 …+26^n)
c * ( 26 * (26 ^ (n+1)-1) / 25)
which is roungly
c26^(n+1)
in terms of Asymptotic big O notation you can write it as O(26^n)

#3

n is basically number of string or length of string??

#4

n is length of string

#5

so if length is n then worst case time complexity is 26^n??

#6

sorry space*…

#7

yeah …
becuase O(26^n) space complexity means space <= C*26^n where C is some constant.

#8

to get this complexity we should assume that the string of length 1 to n-1 are present?? to get that sum 26^1+26^2+…26^n??

#9

read about these notatations here -> https://www.hackerearth.com/practice/basic-programming/complexity-analysis/time-and-space-complexity/tutorial/

#10

see we never get exact space/time while doing analysis thats why we use various asymptotic notation to give a rough estimate about it.

so when someone says that this algorithm has O(26^n) then it means this algorithm can use c*26^n space in worst case.

check the link i have shared above to know more about these notations.

#11

yess sir this thing i got but i am confused in the fact that the string of length should be present from 1 to n-1… because for algorithm like n^2 we can also denote it by n^3 or n^4 for getting upper bound but we restrict ourself till n^2…so in this case also we are restricting till 26^n so 1 to n-1 string can be present in worst case??

#12

yeah … … . … . …

1 Like
#13

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.