[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Length implementation**
**From**: "Soni L." <fakedme@...>
**Date**: Fri, 12 May 2017 16:39:51 -0300

Lua has O(logn) length and searches from the end:
$ lua
Lua 5.3.4 Copyright (C) 1994-2017 Lua.org, PUC-Rio

t={1,2,3,4,5,6,7,8}
for i,v in ipairs(t) do t[i]=nil end
#t

0

for i=8,1,-1 do t[i]=1 print(#t) t[i]=nil end

8
0
0
0
4
0
2
1
Pretty, isn't it?

`I'm not sure what the time complexity of t[#t+1]=v vs t[i]=v is... I
``know the latter is O(n), but the former doesn't seem to be O(n log n)...
``O(n log log n) maybe?
`
--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.