# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

76 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
203 views

172 views

### Help understanding “little o” notation

I have the following homework problem, with given solution but I do not understand why certain choices in the solution were made as opposed to my own (incorrect) solution and I would like some ...
363 views

### Turing Machine that accepts $L=\{a^nb^n | n \geq 1\}$ with at most nlog(n) transitions in 1 tape

I'm having trouble trying to create this machine. I know the answer should go in the way that we always cut in half the number of a's and b's (so the master theorem aplied at $T(n)=T(n/2)+O(n)$ gives ...
51 views

### What is the difference between O(n^2) and O(N)[N*O(1)]?

I was reading this article on gperf. In it they claim that the use of nested if statements for parsing command line input of $N$ options ends up making $O(N^2)$ ...
134 views

### Algorithm to find min pos difference between two integers in an array

The question I'm faced with: Let $A, A, ...,A[n]$ be an array containing $n$ very large positive integers. Describe an efficient algorithm to find the minimum positive difference between ...
76 views

### Pick algorithm with runtime in O(n) vs. Θ(n) vs. Ω(\log n )

You are given three algorithms, $A$, $B$, and $C$ with the following time complexities in the worst case $O(n)$, $\Theta(n)$, and $\Omega(\log n )$, respectively. Assume that you have to choose ...
104 views

36 views

### Find function that satisfy the relation

Can you find the function that satisfy the relation? $$f(n) = \Theta(g(n)), f(n) = o(g(n))$$
23 views

### Time complexity of simple function related to bits

I am wondering about correct answer to this task from a yesterday's test: A function Pow which calculates $y = a^k$ is given, where $k$ is an integer of length ...
23 views

### Asymptotics and logarithms/exponents

We have four categories: additive constants, multiplicative constants, polynomials, and exponentials When determining the growth order of functions, we only care about polynomials and ...
12 views

### Mapping every character to its next occurrence based on the number of unique characters between the occurrences

To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
31 views

### Deducing $3^f = o(3^g)$ from $f = o(g)$

I really need help solving the following question: Given: $$f(n) = o(g(n))$$ Prove: $$3^{f(n)} = o(3^{g(n)})$$ My attempt: I know that $\frac{f(n)}{g(n)} \xrightarrow{} 0$. I need to ...
25 views

### Calculating the Complexity of a Two Part Algorithm

This is in relation to this post I made. I eventually solved this by the following approach: Take the un-ordered file with all the purchasing data and use the UNIX ...