HW3 question3 main thread

Hey,

In general,

is n^4*(log n)^2 = O(n^4*(log n)^2)?

Maybe its better to ask :

is n^x*(log n)^y = O(n^x*(log n)^y)?

10X in advance,

can also, can i say (for example) : O(4^n) > O(2^n)?

As for your 1st question - can you find the appropriate constants mentioned in the definition of O?

and can you generalize this to any function, i.e.

f(n)=O(f(n)) ?

As for the second question, you should clarify what you mean by O(…) > O(…). Do you mean that 2^{n}=O(4^{n}) but not vice versa? can you prove / disprove that (again, using the definition of O)?

I guess, n0=1 and c=1 will work both cases.

I meant that i couldn't find anything below that, and that was actually my question : is that O tight? or could there be something better? in my opinion no, but i'd like to know that for sure.

about the second question, i'll say that n0=1 and c=1 will be good in order to prove 2^n=O(4^n).

on the other direction, is it enough that lim 4^n/2^n when n->inf. is inf? that means that there is n>n0 for which to every c 4^n >2^n. am i correct?

and the question behind the question is can we use what we saw in class about "ranking" of complexities?

we said that 4^n is more to the right than 2^n on the line that was drown. i thought it meant that automatically 4^n>2^n.

10x again,

Always, f=O(f) is tight. It is tight in the sense that any other function f_{2} which is "really smaller" than f does not satisfy f=O(f_{2}).

But how should we define "really smaller" ? The common definision is that the limit f_{2}/f tends to zero.

This notion is very common and useful, denoted "small Oh".

That is: f_{2}=o(f).

Can we use the built in pow() function of python in question 2?

This question was already answred under the relevant thread (Q2).

when you write "log" in the exercise do you mean log with base 2?

In computer science they usually do want you to think on log with base 2 (because of the binary representation of numbers) but you should understand it doesn't matter at all, because of the following equation: $log_a(n)=\frac{log_b(n)}{log_b(a)}=\frac{1}{log_b(a)} \cdot log_b(n)=O(log_b(n))$

i know this equation (: but if they don't want log with base 2 then an explanation to one of my answers would be a bit longer…

in d, can i use the definition of a riemann sum?

(the LHS is a riemann sum of RHS and is bigger then RHS's integral so if ill show RHS is too small to be O(integral of RHS) im done (: and it really just takes 2 lines…)

and obviously rhs <= lhs

and that's why lhs=O(rhs) (:

so.. course staff- Is it allowed to use riemann sums in this question? (that's how we solved such things in the combi course…)

אני חושב שבסעיף ד' סכומי רימן הם כלי קצת יותר (יותר יותר יותר) מידי "משונה" כדי לפתור את השוויון שהוא באמת

לא קשה מידיי אם עובדים בצורה מסודרת עם קצת אלגברה (תיכונית אפילו) הגדרת הסכום (מה זה בכלל סיגמה!?!?) ונוסחה אחת פשוטה גם מימי התיכון.

אני חושב שרמזתי מספיק…

עריכה -

אני לא טוען שהשווין בשאלה נכון/לא נכון אם משהו מהנ"ל השתמע מדברי חו"ח

Do the proofs have to be completely formal? Or can we just show how we found C, N(0) algebraically in a neat manner?

I am not sure I understand what is "completely formal" and "neat manner".

Would you explain?

1. if i have this equation: 2*logn < 3*logn i need to exlpain why its true..?

2. do i have to explain rules of logarithm when i use it?

3. do i need to explain something like n^a != O(n^b) fot a>b, and if i do , will that satisfy: n^k=O(n^k) therefore, for any i<k :

n^k != O(n^i)

tnx :)

1. well, explaining why 2*logn < 3*logn is equivalent to explaining why 2<3…

2. no. Any basic known rules (logarithms, exponents, sums of known series, etc.) do not require explanation.

3. no.