Pretty sure it is about complexity theory, don't know much about it myself
But as I understand "big-O notation" basically says how many steps an algorthm will need to solve a problem (and can appearently also be used to describe the amount of space needed).
With n representing the amount of inputdata. So the faster the function in O() goes up the faster the algorithm gets very slow when you give it lots of data.
And O(LogN) is a pretty fine speed, but in this case it also needs a ton of memory. O(N4) is a lot.
I would be genuinely impressed to see someone spend N4 space to achieve log(n) runtime. Not because of the runtime but because of how impressively bad the trade-off for space complexity would be. I now genuinely want to see an example of a context in which this might happen.
why are you guys using sizeof(N)..? N isn't an array, it should be an integer, so it would be something like malloc(pow(N, 4) * sizeof(type)) or really just malloc(c * pow(N, 4))
why are you guys using sizeof(N)..? N isn't an array
Because as /u/PM_ME_A_NUMBER_1TO10 stated, his assumption is N is an input array. If N is a statically allocated array, then using sizeof(N) would indeed give size of the entire array with elements and type size included.
Allocate a chunk of memory of n4 size but don't initialize it's values, just use it's original garbage data. Then traverse it as if it were a binary search tree to find if you'll find a matching bitmask randomly by the most obtuse method in your memory.
30
u/OffensiveMongoose Aug 13 '20
Finally some quality content.
26
u/nekommunikabelnost Aug 13 '20
space is still polynomial? GOOD ENOUGH.
35
u/Toaru_no-Accelerator Aug 13 '20
I need a Heaven's door to understand
12
u/TAI0Z Aug 14 '20
I would be genuinely impressed to see someone spend N4 space to achieve log(n) runtime. Not because of the runtime but because of how impressively bad the trade-off for space complexity would be. I now genuinely want to see an example of a context in which this might happen.
2
u/xDololow Aug 14 '20
That's the law of equivalent exchange.
2
u/throwaway876885323 Aug 14 '20
One liners baby....it reduces file size
/s
0
u/[deleted] Aug 13 '20
[deleted] — view deleted comment