Matrix multiplication over range in $O(n)$

Let $ M$ denote the time it takes to multiply 2 matrices, and $ Q$ denote the number of queries.

Is it possible to create a data structure with $ O((n+Q)M)$ pre-computation time, and can answer range matrix multiplication queries that satisfy $ l_{i-1}\le l_i$ and $ r_{i-1}\le r_i$ with an overall time complexity of $ O((n+Q)M)$ . I’ve been thinking a lot on how to manipulate 2 pointers to get the intended results, but haven’t come up with any approach yet. The matrices are not necessarily invertible.

$O(n)$ algorithm related to contiguous subsequences

I’m given an array $ A$ with $ n$ integers. I need to find total contiguous subsequences (aka subarrays) such that the product of all the elements in that subarray can be represented as the difference of squares of two integers.

Now, we know that any integer can be represented as the difference of squares of two integers if the remainder obtained after division by $ 4$ is not $ 2$ .
Right now, I have a $ O(n^2)$ algorithm with me, where for each element $ A[i]$ , I visit all the elements from $ i-1$ to $ 0$ in that order and check if the remainder is $ 2$ .
Any hints on how to proceed for an $ O(n)$ algorithm?

Time complexity of $O(n)$ loop which has a multiplication ($O(n^2)$) in it

Assume we know that the implementation for the multiplication operator for a language is known to be $ O(n^2)$ .

Given this pseudocode:

func wibble_wobble(List<Integer> input):     Integer constant = input.length;     return List<Integer> { item * constant foreach item in input }; 

Since the loop inside the new list initialization is $ O(n)$ , but the multiplication operation inside is $ O(n^2)$ , is this function considered to have a time complexity of $ O(n)$ , $ O(n^2)$ , or maybe even $ O(n*n^2)=O(n^3)$ ?

My gut instinct says it is $ O(n)$ because a change in input would not change the time complexity of the multiplication operation, and thus would not need to be considered, but I am not sure.

Do there exist any problems with optimal algorithms beyond $O(n)$?

Blum’s Speedup Theorem famously shows that there are problems which admit no fastest algorithm. This raises an obvious question: are there any problems that do admit a fastest algorithm? In other words, does there exist a language $ L$ which is decided by some algorithm within $ f(n)$ steps so that any other algorithm which solves the same problem also runs in $ \Omega(f(n))$ steps? If $ f$ is linear, this is trivially the case. But what about beyond linear? Just a nonconstructive existence proof would already be cool.

How can I make my js app run using one “on click event” instead of four?

I’m a few weeks into javascript and had to make a simple “crystals collector” app. The app works as intended, but the code is obtuse and repetitive.

I’d like to make the app work using just one on click event, rather than using four for each crystal. I can’t make an array of each color crystal and loop through them since the num variables change as well.

Sorry for such a rudimentary question, thanks for any advice.

Here is my code below:

$  (document).ready(function () {      // Global variables          var targetNumber;     var num1;     var num2;     var num3;     var num4;     var userTotal = 0;     var wins = 0;     var losses = 0      // Functions      function reset() {         num1 = Math.floor(Math.random() * 11 + 1);         num2 = Math.floor(Math.random() * 11 + 1);         num3 = Math.floor(Math.random() * 11 + 1);         num4 = Math.floor(Math.random() * 11 + 1);         targetNumber = Math.floor(Math.random() * 101 + 19);         userTotal = 0;         $  ("#total-score").text(userTotal);         $  ("#target-score").text(targetNumber);     }      function initialize() {         num1 = Math.floor(Math.random() * 11 + 1);         num2 = Math.floor(Math.random() * 11 + 1);         num3 = Math.floor(Math.random() * 11 + 1);         num4 = Math.floor(Math.random() * 11 + 1);         targetNumber = Math.floor(Math.random() * 101 + 19);         $  ("#target-score").text(targetNumber);         $  ("#wins").text(wins);         $  ("#losses").text(losses);         $  ("#total-score").text(userTotal);     }     function logic() {         if (userTotal === targetNumber) {             alert("You Win!");             reset();             wins++;             $  ("#wins").text(wins);         }         else if (userTotal > targetNumber) {             alert("You lose!");             reset();             losses++;             $  ("#losses").text(losses);         }     }      // Run Game (main)     // something like...     // var array = ["#blue","#green","#red","#yellow"]     // for (var i =0; i < array.length;i++) {     // }      initialize();      $  ("#blue").on("click", function () {         userTotal = userTotal + num1;         $  ("#total-score").text(userTotal);         console.log(userTotal);         logic();     })      $  ("#green").on("click", function () {         userTotal = userTotal + num2;         $  ("#total-score").text(userTotal);         console.log(userTotal);         logic();     })      $  ("#red").on("click", function () {         userTotal = userTotal + num3;         $  ("#total-score").text(userTotal);         console.log(userTotal);         logic();     })      $  ("#yellow").on("click", function () {         userTotal = userTotal + num4;         $  ("#total-score").text(userTotal);         console.log(userTotal);         logic();     })    });
.img {     width: 150px;     height: 150px; }  #crystal-main {     width: 650px;     border: 2px solid gray;     padding: 25px;     background: black;     color: whitesmoke; }
<!DOCTYPE html> <html lang="en">  <head>     <meta charset="UTF-8">     <meta name="viewport" content="width=device-width, initial-scale=1.0">     <meta http-equiv="X-UA-Compatible" content="ie=edge">     <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css"         integrity="sha384-ggOyR0iXCbMQv3Xipma34MD+dH/1fQ784/j6cY/iJTQUOhcWr7x9JvoRxT2MZw1T" crossorigin="anonymous">     <link rel="stylesheet" href="assets/css/style.css">     <title>Crystal Game</title>     <script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.2.1/jquery.min.js"></script>     <script src="assets/javascript/game.js"></script> </head>  <body>     <h1>Crystals Collector!</h1>     <hr>     <div class="container-fluid">         <div class="container" id="crystal-main">             <div class="row">                 <h2>Target Score: <span id="target-score"></span></h2>             </div>             <div class="row">                 <h2>Total Score: <span id="total-score"></span></h2>             </div>             <div class="row">                 <div class="col-3-md crystal">                     <img src="assets/images/blue.png" alt="blue" class="img" id="blue">                 </div>                 <div class="col-3-md crystal">                     <img src="assets/images/green.png" alt="green" class="img" id="green">                 </div>                 <div class="col-3-md crystal">                     <img src="assets/images/red.png" alt="red" class="img" id="red">                 </div>                 <div class="col-3-md crystal">                     <img src="assets/images/yellow.png" alt="yellow" class="img" id="yellow">                 </div>             </div>             <div class="row">                 <h4>Wins: <span id="wins"></span></h4>             </div>             <div class="row">                 <h4>Losses: <span id="losses"></span></h4>             </div>         </div>     </div>  </body> </html>

Covering lemmas in Hochman’s “On self-similar sets with overlaps and inverse theorems for entropy”

I am confused about the covering lemmas in the captioned work and really hope to get some ideas here.

Firstly it is lemma 3.7. (Image of Lemma 3.7) (for convenience here is the lemma of this lemma (Image of Lemma 3.6))

I do not understand the ”$ \supseteq$ ” in the line ”$ J’\cap(J’-\ell)\supseteq \cdots$ ”. Also I am wondering if the following provides a counter-example of this line and this lemma:

Let $ n=12$ , $ I=\{0,1,2,3,4,5,6,7,8\}$ , $ m=3$ . Then $ I’=\{0,4,8\}$ by the construction in Lemma 3.6. Let $ J=\{0,2,4,6,8,10,12\}$ , $ \delta=0.5$ . Then for all $ i\in I$ , $ |[i,i+3]\cap J|=2\geq(1-\delta)m$ . Take $ \ell=1$ . Then for all $ J’\subseteq J$ , we have $ J’\cap(J’-\ell)\subseteq J\cap(J-\ell)=\emptyset$ , $ \bigcup_{i\in I’} J\cap[i,i+2]=\{0,2,4,6,8,10\}$ , and $ (1-\delta-\frac{\ell}{m})|I|=(\frac{1}{2}-\frac{1}{3})\cdot 9 >0$ .

Secondly, it is lemma 3.8.(Excerpt for Lemma 3.8), which I am not sure how the marked inequality is obtained.

Since subsequent results depends on these lemmas and this paper is already acknowledged in the field, I think there should be an answer for resolving my confusion.

Thanks for help!

Is there a less than $O(n)$ algorithm for converting UTF-8 character offsets to byte offsets, in a gap buffer?

A Gap Buffer is a variation on a dynamically-sized array, but with a gap inside it. The gap makes editing operations around the gap more efficient. Deletion before the gap can be implemented by simply making the gap larger for example.

UTF-8 is a variable width encoding for text. The first bits of the first byte of a character describes how many bytes are in the character, to a maximum of four.

When describing a cursor position in a string, (specifically a position between characters), we can use a pair consisting of the line number, (let’s say we start at zero), and the horizontal character offset (how many characters to the right the cursor is from the position to the left of the first character on the line). It is useful to use this representation to position a cursor.

However, in order to move the byte offsets that determine where the buffer’s gap is we need to convert the line number and character offset to a byte index.

The best way I currently know how to do this is the following $ O(n)$ algorithm:

Call the line number and character offset we are looking for the byte offset of, "the target".  Keep track of the current line number and character offset as we go, starting each at 0.  for (the characters before the gap) {     if the current line number and character offset matches the target,         return the byte offset. }  if the space right after the last character before the gap matches the target,     return the byte offset of the start of the gap.  for (the characters after the gap) {     if the current line number and character offset matches the target,         return the byte offset. }  if the space right after the last character after the gap matches the target,     return the byte offset of the end of the buffer.  Otherwise, the cursor is out of bounds. 

This is all under the assumption that the buffer is well-formed. That is, the gap starts immediately after a UTF-8 character, and the gap ends just before another one, or the end of the entire buffer.

Is there a way to do this with a lower computational complexity than $ O(n)$ ? If I try to imagine one, the closest I can get is to try something like binary search, but that seems like finding a pivot point (past maybe the first one which we could cache,) would involve iterating over the buffer anyway, so it wouldn’t actually be $ O(\log n)$ .