# Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

9,024 questions
Filter by
Sorted by
Tagged with
35 views

### If is true f(n) = Θ(g(n)) and if f(n) = o(h(n)) then g(n) = o(h(n))?

In asymptotic notation the transivity holds, however what happens when we have small o such as if f(n)= o(h(n)) does that means that also g(n)=o(h(n)) holds? i take as granted that both of f(n)=o(h(n))...
20 views

### Find the intersection point between two sorted arrays with unknown lengths in lesser than O(n)

Two sorted arrays of positive integers, X[] and Y[] are given.But, the array sizes are unknown to us. We may assume that accessing any index beyond the last element of the array returns -1. The ...
24 views

### Finding loop invariant

I am really new concerning loop invariants and I am currently trying to figure out a loop invariant of an algorithm for prime numbers. I tried a lot of ideas, but I still have problems since there are ...
16 views

29 views

29 views

### Prove that two vertices are in the same connected component of G if a vertex or his decedent has a step ancestor

Given the forest $G_\pi$ of a DFS run on an undirected graph $G=(V,E)$ and a simple path from a root to a descendant $u_0 \rightarrow ...\rightarrow u_k$. Define $w$ as a step ancestor of $v$ if ...
27 views

### Machine learning algorithms for recognising national anthem song of all countries

https://en.wikipedia.org/wiki/National_anthem Are there machine learning algorithms which will recognise and interpret the national anthem song of all countries? Input dataset : National anthem sound ...
2k views

### Are there any functions with Big O (Busy Beaver(n))?

So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than ...
61 views

### Are logarithmic Big-O complexities defined with constant base equal to those defined with variable base?

Example: Deleting from a B-Tree (not to be confused with binary tree) has Big-O complexity of $O(\log_t n)$ (where $t \in \mathbb{N}$ is the order of the tree). There was one true/false question on ...
22 views

### Modify a binary matrix to minimize the sum of values of the rows

I have a matrix of zeros and ones, i.e., $\mathbf{X}=[x_{ij}]$ with $x_{ij}\in\{0,1\}$ for all $i=1,2,\ldots,m$ and $j=1,2,\ldots,n$. Associated with each row $i$ of the matrix $\mathbf{X}$ a set of ...
41 views

### Calculating a jackpot winner based on probabilities

Imagine a jackpot where users can bet as much as they want, and each bet increases their winning chance. Given a roll [0-100], how would you calculate the winner? ...
21 views

### asymptotic tight bounds for quadratic functions

In Introduction to Algorithms by CLRS, it's said For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, ...
22 views

### Unconstrained subset sum vs constrained subset sum?

In class, we discussed two question types: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by. Question 1: ...
33 views

### Is “backward substitution” and “backtracking” the same thing?

From my limited knowledge, they both are related to solving recurrence relation. Solving recurrence relation using backward substitution Solving recurrence relation using backtracking Can the terms ...
19 views

### Solving multiple pathfinding problems efficiently

Let $V$ be a set of nodes, $c : V \times V \rightarrow \mathbb{R} \cup \{\infty\}$ be an edge cost function, and $h : V \times V \rightarrow \mathbb{R}$ be an admissible heuristic. Suppose we want to ...
27 views

### Big O of my backtracking solution

I have a problem and I've been struggling with my solution time and space complexity: Given an array of integers (possible duplicates) A and ...
108 views

### Is there a linear sorting algorithm given an oracle that finds kth smallest item?

Given a machine that can compute the kth smallest item of an Array A in $O(\sqrt n)$ time. Find a recursive function that can sort A in linear time corresponding to $n$ which is the length of A. First ...
64 views

38 views

### Asymptotic running time function's domain

I am reading CLRS and have uncertainty in asymptotic running time of algorithms. In CLRS, it is said, The notations we use to describe the asymptotic running time of an algorithm are defined in terms ...
29 views

### Solution to T(n) = 2T(n/2) + log n

So my recursive equation is T(n) = 2T(n/2) + log n I used the master theorem and I find that a = 2, b =2 and d = 1. which is case 2. So the solution should be O(n^1 log n) which is O(n log n) I looked ...
I haven't been able to find whether this problem has been studied: we are given a graph $G$ and an ordered list of $k$ colors $L = [\ell_1, \cdots, \ell_k]$. Additionally, we are given a positive ...
So I just started learning greedy algorithms and I have a problem that I want to solve. The statement is as follows: In your calendar you have an $L$ list of all the tasks you need to complete today. ...