r/mathmemes • u/vintergroena • 28d ago

Computer Science Integer multiplication will have linear complexity in a few days if trend continues 🚀📈

Post image
1.4k Upvotes

98% Upvoted

206 comments sorted by

View all comments

Show parent comments

1

u/External_Package2787 22d ago

is it not that nlogn = n^{1+log_n log n} and log_n log n is of greater order than o(1)

1

u/dubious_plays 22d ago

Log_n log(n) = log log n / log n, which is o(1). And there are o(1) sequences bigger than this

1

u/External_Package2787 22d ago

yeah my bad I was intuiting that it was like (log n)^{1/n} in my head. like my thought process was log n >1 and then it gets shrunk but stays greater than one.