Mathematics

12:28 AM

What are you up to @usukidoll? Still need some help?

Though looknig over it it seems you reached the step before the final one.. Just need to use the definition of $+$ (symmetric difference I assume) again over that

qwr

I don't follow the forefront of mathematics, do you think any big math problems will be solved in the next 50 years?

Jesus Salas

Hi there

I need some help with Time Complexity stuff

what kind of complexity is O(N Log(4)) ?

qwr

4?

just 4?

Jesus Salas

well, every time I double N it takes four times more time

qwr

that's n^2?

Jesus Salas

12:41 AM

yes,

is like n^2

so it is quadratic time?

and if it is O( N Log(3) ) or N^1.585?

I'm not very good on all this but I'd like to know what is the complexity time for an algorithm I developed

Studentmath

hmm, I am a bit uncertain @JesusSalas

Jesus Salas

ok, I'll try to explain myself

Studentmath

But I -think- they usually take the n itself as it is, and disregard the rest, for guesstimating

Or well

Generally.

For example, if T(n)=log2*n^2+321321n

Mike

@qwe sure

Studentmath

They would say O(N)=n^2

We are sepaking about the same thing here, right?

Jesus Salas

12:46 AM

I have an algorithm that when I fee a set of 100 numbers to process takes 1 second when I double the numbers (200) takes 4 seconds, if I double again (400) it takes 16 seconds, for 800 takes 32 seconds

qwr

@Mike sure to my question?

Jesus Salas

and I'm wondering how to represent this time complexity using O(..)

@studen

qwr

@Mike like the riemann hypothesis or navier stokes equations. I would love to see it solved in my lifetime

Jesus Salas

@Studentmath I really don't know :) this is why I'm asking

Studentmath

I see, hmm

I would use recursive function to describe it, I think.

O(100)=1

Assuming of course the set of numbers is always at the doubles of 100

And then T(n)=4*T(n-1) for the rest

That would be

T(100)=O(1)

where n={100, 200, 300, 400....}

I am hoping I am not only confusing you, if it is not the case (doubles of 100) then it's probably not the right way to do it

Jesus Salas

12:51 AM

we can use 1 as a start point :)

1,2,4,8,16,32

everyt time I double N it takes 4 times the previous time,

Studentmath

Then yes, I will use recursive function for that.

Jesus Salas

T(2N) = 4T(N)

Studentmath

Hahhh... I see.

Disregard all I said before.

Jesus Salas

this sound more right to you?

Studentmath

It sounds right but it doesn't define it well, I think.

I would say:

Jesus Salas

12:54 AM

probably not :D

Studentmath

T(n)=c, n=1

T(n)=2T(n/2), n>1

where c is whatever T(1) is, of course

Looks very alike to the general merge-sort reccurence equation

MickLH

Hey guys, quick error check if someone doesn't mind. I've got an array $L_x$ which represents the values of a function $W(x)$ at integer values

Studentmath

Does this make sense to you?

MickLH

I've developed a routine to approximate $\int_a^b W(x) dx$

this is it:

$\sum_{x=\lfloor a\rfloor}^{\lfloor b\rfloor-1}(\frac{L_x + L_{x+1}}{2})
+\frac{(\lceil a\rceil-a)(L_{\lceil a\rceil} + L_a)}{2}
+\frac{(b-\lfloor b\rfloor)(L_{\lfloor b\rfloor} + L_b)}{2}$

Am I being stupid?

Jesus Salas

@Studentmath well, math never fails...

Studentmath

12:59 AM

Not if it is done right :P

MickLH

My idea is that I am approximating the integral by summing the trapezoid formed by each two adjacent samples

Jesus Salas

so it seems complexity if O(N^LOG(4)) that result in O(N^2), what means quadratic time

and O(N^Log(3)) results in O(N^1.585) that means linearithmic time

MickLH

As well as creating "edge" trapezoids to account for non-integer values of $a$ and $b$

Studentmath

Makes sense, assuming you use log with base 2

Jesus Salas

yes I do

Studentmath

1:02 AM

Alright, go on

Jesus Salas

Thank tou so much!

*Thank you

Studentmath

Ah, erm.. You're welcome I guess! Not that I did much but just follow your line of thought :P

Nick

1:33 AM

Hi guys, a quick question on terminology. What is that fundamental approximation called where you sandwich a value between a lower point and an upper point till you get a descent approximation.

Brandon Enright

@Nick Squeeze theorem or related?

Nick

$9 < (3.5)^2 < 16$

and you work your way to finding the middle value

Brandon Enright

@Nick I'm still guessing here but I'd call that "bounding the result". You know it's between two values so you keep going until you find something in the bounds.

Nick

Yeah, good enough

@BrandonEnright: Newton's approximation for a square root is kinda like that, right?

... oh nope, he used calculus more than I thought.

Brandon Enright

@Nick I dunno. I'd call that iterative convergence.

Nick

1:40 AM

@BrandonEnright: Good name. :D

@Brandon: How would you go about finding the value of $10^{0.3010}$

Mike

@Nick Put it into a calculator