big o question | Mathematics | Page 1

stable archBOT Jun 2, 2024, 11:22 AM

#

stray plinth Jun 2, 2024, 12:16 PM

#

First, what affects the time complexity in that code snippet?

#

How'd you do the inner loop?

#

Yeah yeah!

#

Same thing for the outer loop.

#

We start with i = 3 and are squaring it just before i becomes greater than N.

#

true, it's not directly the same, but the idea follows

#

Look at how i changes

#

i = 3
i = 3^2 = 9
i = 9^2 = 81
i = 81^2 = 6561
etc

#

So generally, after k iterations, I becomes 3^2^k

#

yes!

#

but, our loops sets i to 3

#

so we get log base 3 of n

#

specifically we get this from looking at how i changes: 3^(2^k)>N

#

you're close!

#

this is part of it

stray plinth Jun 2, 2024, 12:24 PM

#

stray plinth So generally, after k iterations, I becomes 3^2^k

the key lies here, in how i changes

#

Do you get how we got this? 3^(2^k)>N

#

haha no worries

#

Oh fantastic!

#

YES

#

haha

#

you're awesome

#

but slow your role there lad

#

3^(2^k)>N

We want to solve for k

#

This solved for n, we want to solve for k.

#

As in: N = log3(log2(k)

#

we want k = ...

#

gotcha! Best of luck. Been a while since I've done o complexity

#big o question