# Tagged Questions

Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

11 views

### Find largest value of the constants that makes the equality true

$$sin(h^2) = a + O(h^b)$$ Find the largest value of a and b such that the equality holds. I tried to use the truncated Taylor series expansion of $sin(h^2)$, but the derivatives of the function are to ...
22 views

29 views

### How to show the running time of the following algorithm? [closed]

The outer loop runs n times. The inner loop runs Math.floor(n/i) times. So it would be O(n*Math.floor(n/i)). I do not know how to transform that into a proper expression involving Big Oh and n. Maybe ...
12 views

### What is the complexity of the arithmetic operations in base $b$?

Fix a number $n$. We want an algorithm which takes a positive integer $x$, represented as a base $b$ string, and outputs the base $b$ representation of $nx$. Note that if $n$ is a power of $b$, there ...
31 views

48 views

### Meaning of “polynomially larger”

For example Is $n$ polynomially larger than $\frac{n}{\log n}$? Than $n \log n$? Is $n^2$ polynomially larger than $\frac{n}{\log n}$? Than $n \log n$? I am trying to understand the difference ...
49 views

### Simplify sum with binomials

An algorithm finds prefixes of given length k from given word with length n. It is required to find the time complexity of given algorithm. It is easy when no nodes get cut off in its recursion tree (...
I have the following assignment on my Algorithms Analysis course. Given two undirected graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ with $\operatorname{card} (V_1) < \operatorname{card} (V_2)$ ...