Question

Find the least integer n such that the specified function is O(x^n)

Answer 1

I think both functions are \(\large \mathcal{O(1)}\), so \(n = 0 \)

Answer 2

This class is going to kill me. I don't even understand to well that they want me to do :(

Answer 3

\[\large g(x) = \dfrac{(x^2+2)\log x + 3x^2}{2x^3-1}\]

\[\large = \dfrac{\mathcal{O(x^2\log x)}}{\mathcal{O(x^3)}}\]

Answer 4

as the size of data, x, varies, the numerator complexity varies as x^2log(x) and the denominator complexity varies as x^3

Answer 5

we can disregard the -1 right?

Answer 6

nce all the terms are less than 1 coefficient hence the function will be O(1), since the maximum value of log(x) < x, hence big-oh of function will be O(X^0) and a = 0

Answer 7

is that right?

Answer 8

that looks good to me ^

Answer 9

for the second one.. what about this ..

Answer 10

a class mate says it is -1 ... as we ignore the -1 and associate the values

Answer 11

that the function would be O(X^-1)

Answer 12

i think so, -1 should be correct

Answer 13

but i don't understand how he gets to that conclusion :(

Answer 14

this class is so hard. I think I may have to drop it

Answer 15

\[\large h(x) = \dfrac{x^2+2}{2x^3\log x-1}\]

Answer 16

listen, its not that hard - tbh, idk these stuff, i just googled and discussing with you as they seem interesting

Answer 17

\[\large h(x) = \dfrac{x^2+2}{2x^3\log x-1}\]

\[\large ~~= \dfrac{\mathcal{O(x^2)}}{O(x^3\log x)}\]

Answer 18

numerator complexity is x^2,

Answer 19

denominator complexity is atleast x^3logx = x^3x^k = x^(3+k)

0<k < 1

Answer 20

Overall function complexity is :

2-3-k = -1-k = -1.something

Answer 21

ceiling it to highest value gives -1

Answer 22

Hmm You explain so much better!

Answer 23

my book and class notes are so confusing . Even at 4 AM I understand you better! I see what you are doing.. it is like finding a bounding max function? right?

Answer 24

Exactly !

Answer 25

for example :

complexity of \(\large f(x) = \dfrac{x^3+1}{2x}\) would be \(\large \mathcal{O(2)}\)

Answer 26

we move the integers... bring all the exponents in one line.. kinda the magic number!

Answer 27

2x and 1000000000x are same
when we speak about complexity

Answer 28

both are polynomial time of order 1 (linear)

Answer 29

I feel this better now!

Answer 30

similarly, x^3 and x^3+2x are same

Answer 31

x^3 and x^3 + x^3 are also same

Answer 32

we look at the highest exponent ?

Answer 33

yes...

Answer 34

cool! Can I ask you one last help with this let me see if i get it

Answer 35

here the highest exponent is x^3... so it is 3rd order?

Answer 36

yes but thats already given, the problem wants you to prove it by finding the values of C and K

Answer 37

the definition is |f(x)| ≤ C|g(x)| for x ≥ k.

Answer 38

g(x) would be x^3 , right? bcs that is the variable with the highest exponent?

Answer 39

like this ?

\[\large |2x^3+3x\log x| \le C|x^3|\]

Answer 40

I think so. I am not too sure what is the right f(x) to use

Answer 41

or how to move next

Answer 42

our goal is to find \(C\) that holds above inequality for all x = k > 1

Answer 43

\[\large |2x^3+3x\log x| \le C|x^3|\]

\[\large \dfrac{|2x^3+3x\log x|}{|x^3|} \le C\]

Answer 44

\[\large |2x^3+3x\log x| \le C|x^3|\]

\[\large \dfrac{2x^3}{x^3} + \dfrac{3x\log x}{x^3} \le C\]

\[\large 2 + \dfrac{3\log x}{x^2} \le C\]

Answer 45

Cool. I follow that. so C is greater than 2 for sure!

Answer 46

make it :

C >= 2+3 = 5
k >= 1

Answer 47

cos the upper bound of 3logx/x^2 is 3

Answer 48

is that because we are letting x = 1?

Answer 49

ahhh

Answer 50

yes i think you knw more about these things than me lol

http://www.wolframalpha.com/input/?i=max+3log%28x%29%2Fx%5E2

C >= 2+1 = 3
k >= 1

will also work

Answer 51

but C>=2 will not work.

Answer 52

the minimum value for C to satisfy the initial inequality for all x=k>=1 is C = 3 ^

Answer 53

so k = 1 and c =3 ?

Answer 54

that works :
http://www.wolframalpha.com/input/?i=solve+2x%5E3%2B3x%5Clog+x+%5Cle++3x%5E3+in+reals

Answer 55

awesome! I understand better now

Answer 56

thank you so much !

Answer 57

Are you familiar with recursion by any chance?

Answer 58

np :) try me...

Answer 59

This is even weirder lol

Answer 60

Basis : consider this 4 bit string \(\large "t010"\)

Answer 61

(btw you did great with the c = 3 :D you rock!! )

Answer 62

From the hypothesis, we have \(\large w="010" \in S \)
Also from the hypothesis recursion step, we know that \(\large "0"w\) and \(\large "1"w\) also will lie in \(\large S\)

Answer 63

that means, all the strings with \(\large 1\) bit prefix substring (\(t\) ) will lie in \(S\)

So the statement is true for \(1\) bit suffix substring \(t\)

Answer 64

that establishes the base case ^

Answer 65

that means a 0 left to w like 0010 and a 1 left to 1 like 1010 ?

Answer 66

let me know if something doesn't make sense

Answer 67

yes ! those are all the possible values for \(1\) bit suffix substring \(t\)

Answer 68

when t is 1 bit,
t = 0
t = 1

are the only possible values

Answer 69

so "t010" covers all the possible 4 bit strings ending with 010

Answer 70

awesome!

Answer 71

thats the base case ^

now we need to make an assumption, for t = k, and go ahead with proving that the t = k+1 gives all possible strings as well

Answer 72

recall the basic structure of any induction proof :
1) prove n = 1 lies in the solution set
2) assume n=k lies in the solution set
3) prove that n=k+1 lies in the solution set, whenever n=l lies in the solution set.

Answer 73

we're done with step 1, so far

Answer 74

yes! that i do remember well

Answer 75

step2 : assumption/induction hypothesis

Assume that for some prefix string \(t\) of length \(k\), all the strings ending with \("010"\) lie in \(S\)

Answer 76

so we use induction for recursion?

Answer 77

in simple words :
\("t010"\) lies in \(S\)

where \(t\) = all possible substrings of length \(k\)

Answer 78

the last step is to prove the \(k+1\) case using the induction hypothesis

Answer 79

step3 : prove k+1 case/induction step

from the induction hypothesis \("t010" \in S\)
from the given recursion step, \("0t010"\) and \("1t010"\) also will lie in \(S\)
that means all the strings with prefix substrings of length \(k+1\) will lie in \(S\)

QED.

Answer 80

guess its a simple proof, explanation is bit tricky o,o

Answer 81

lol but we need induction for recursion?

Answer 82

we did use plenty of induction above right ?

Answer 83

the question itself asked us to work it by induction, so..

Answer 84

that is true lol so sorry! I misread the second part !

Answer 85

let me put all the 3 steps in one place so it becomes easy to read

Answer 86

thanks! I think you are a wonderful human being! just so you know

Answer 87

*cries*

Answer 88

Statement to prove : prove that \(\large S\) contains all strings ending with \(\large 010\)

Answer 89

Step1 : Base case (show that \(\large "t010" \in S\) when the length of prefix substring equals \(\large 1\)

From the hypothesis, we have \(\large "010" \in S\)
Also from the hypothesis recursion step, we know that \(\large "0"010 \) and \("1"010\) also will lie in \(S\)

that means, \(\large "t010" \in S\) when the length of prefix substring equals \(\large 1\)

Answer 90

Step2 : assumption/induction hypothesis (n=k case)
Assume that for some prefix string \(\large t\) of length \(\large k\), all the strings ending with \(\large "010"\) lie in \(\large S\).

In other words : \(\large "t010" \in S\)
where \(t\) = all possible substrings of length \(k\)

Answer 91

Step3 : prove k+1 case/induction step

from the induction hypothesis \(\large "t010"\in S\)
from the given recursion step, \("0t010"\) and \("1t010"\) also will lie in \(S\)

that means all the strings with prefix substrings of length \(k+1\) will lie in \(S\)

Answer 92

QED.

Answer 93

that looks like a mouthful, have fun :)

Answer 94

you are very kind! Now I am going to take the quiz which is kinda hard but you have helped me greatly ! thanks!

Answer 95

good luck !