Questions tagged [efficiency]

Using as few resources (e.g. time, space) as possible while solving a problem. Use this tag if your question is specifically about resource usage, not for generic algorithm questions that happen to mention running times.

Filter by
Sorted by
Tagged with
0
votes
0answers
14 views

Most efficient way to calculate $\sum_{i=3}^n{S(n)}$, where $S(n)$ is the largest number $m \lt n-1$, such that inverse of $m \% n$ equals $m$ itself?

Problem: Most efficient way to calculate $\sum_{i=3}^n{S(n)}$, where $S(n)$ is the largest number $m \lt n-1$, such that inverse of $m \% n$ equals $m$ itself? So, what I understand from this ...
0
votes
1answer
26 views

The interpretation of expected time bound for searches in a hash table

As CLRS book,page 260 stated, Thus, the total time required for a successful search is $\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$ I wouldn't have any problem if the author says ...
1
vote
1answer
18 views

Number of operands to take when evaluating postfix notation?

All sources I have seen list taking two operands from the stack once we encounter an operator. Why? What if not all of my operators are binary (taking two arguments)? What if I have custom unary and ...
3
votes
1answer
92 views

Merging Tuples of Intervals

Suppose I have a list of tuples. Each tuple contains 2 intervals. The intervals in each tuple have nothing to do with each other. I would like to find a smaller list of tupels that covers all elements ...
-3
votes
1answer
61 views

How to design fast/efficient algorithms?

Let's say, if you could travel to the past, what would you teach your younger self? Which key points define efficient algorithms?
1
vote
2answers
93 views

Fast computing of a matrix power for large integer values in C++

I'm working with squared matrices that can be quite large, for instance, a M = 50 x 50 matrix. My objective is to compute the power of the squared matrix ...
0
votes
0answers
17 views

Counting distinct elements in array using hash table and measuring efficiency

I need to implement an algorithm to solve the Count-distinct problem given an array of $N$ elements using a hash table, and devise metrics with which to measure my algorithm efficiency. I was told I ...
1
vote
2answers
75 views

Efficient way to find key points on spline to approximate it with line strip

Given a spline, what is an efficient way to find (approximately) the least amount (and position) of key-points to approximate the spline with a line strip, so that the largest distance between the ...
0
votes
1answer
24 views

How can we solve halting problem efficiently?

I was doing exercises regarding the halting problem and there is this question where I am stuck Ques: it goes like suppose if you can decide the halting problem with a query "Is <tm,s> ...
0
votes
0answers
37 views

Efficient method for finding 1's in binary representations

Say I have a binary number of N bits, and I need to find every combination that have M 1's. For example, if N = 3 and M = 1, then 100, 010, 001 are the allowed combinations. I have read that a more ...
1
vote
0answers
25 views

Which of the query approaches are more efficient?

There are two relations, registered(participant,topic) and fee(participant,amount). The primary key for registered is (participant, topic) and the primary key for fee is participant. The premise is ...
0
votes
1answer
19 views

About the connection of pipelined execution and latency

Let's consider we want to calculate a[i]=a[i]*c for a vector the size of N=12 on some random processor. We do assume that ...
10
votes
1answer
1k views
1
vote
0answers
61 views

Can we make at most 3 comparisons in the closest points algorithm instead of 7?

Let's say I am using the divide and conquer algorithm outlined here, but I only want to return the minimum distance. I understand why that algorithm puts an upper-bound at 7 but I think that can be ...
0
votes
0answers
52 views

Efficient triangular decomposition of an integer

Euclidean division is an iterative process that has been made super-efficient at the CPU level, right? Its specification is that if I do (q, r) = f(n, d), I get ...
1
vote
2answers
44 views

Floating-point oblivious way to compute multiset numbers

I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be: $$ R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{...
0
votes
1answer
124 views

Making an algorithm that picks a unique random number in fixed set more efficient

I have been working on a project that simulates an online bank. At this point, I'm implementing the code used to create user accounts. Each account will have a sortcode and account number, I have ...
1
vote
0answers
61 views

Convex hull on set of squares

Imagine a set of two to six squares within 3D-space. The goal is to generate a convex hull around these squares as efficiently as possible. The following constraints are known: Each of the two to six ...
1
vote
1answer
52 views

Overhead cost of spawning child processes

I am curious as to the overhead cost of spawning child processes using fork in a Linux environment. Suppose I have a C program such as ...
2
votes
3answers
136 views

Faster computation of $ke^{-(x - h)^2}$

The question is quite simple; almost every computer language today provides the $\exp(x)$ function in their standard library to compute expressions like $ke^{-(x - h)^2}.$ However, I would like to ...
-1
votes
1answer
157 views

Finding most efficient sorting algorithm

Arr is an array that contains $ n$ numbers. Suggest the most efficient algorithm for each case and analyze the runtime. Explain why the algorithm you chose is the best one. Arr contains exactly $\...
0
votes
3answers
64 views

Big O Proof , f(n) = 2n + 1 and I have to prove f(n) is O n^2

If I have $f(n) = 2n + 1$ and I have to prove $f(n) \in O(n^2)$, by proving there exists positive constants $c$ and $n_0$ such that $f(n)<cn^2, \forall n\ge n_0$, can I do this all in one step by ...
0
votes
1answer
84 views

How to prove Big-O when $F(N)$ is even or odd

If I'm given a function $f(n)$ which is for example $4n+1$ when even and $3n^2+2$ when odd and I have to prove or disprove $f(n)$ is $\mathcal O( n^2 )$. Do I have to do $f(n) < c n^2$ for all $n &...
-2
votes
2answers
38 views

Calculating efficiency?

A program must construct and then use a set $S$ of 1000 integers. ...
0
votes
1answer
48 views

Efficient algorithm to compare arrays problem

I was submitted an interesting problem, but I wasn't able to find a solution. Define a function p(x, y) that takes int x and y, with ...
1
vote
1answer
36 views

Understanding recursion tree for withdrawal formula

$$ T(n) = T(n-a) + T(a) + cn $$ Now the solution says that the height of the tree $(h)$ is: $$ h = \left \lfloor n/a \right \rfloor $$ And I don't understand why. Maybe I didn't understand the ...
0
votes
1answer
29 views

Why substituting the search part in INSERTION SORT doesnt yield a running time of $\Theta(nlgn)$

$$ \Theta - Tight \ asymptotic \ bound $$ If we change lines $5-7$ in Insertion sort With BINARY-SEARCH(A,p,r,v) Why don't we get a running time of $\Theta(n\lg n)$ as we go through the array $\...
1
vote
2answers
118 views

What's the most time efficient way to find the number of nodes reachable from each root and no other root?

Suppose there are n nodes. These nodes are connected by m unique directed edges. Sets of these edges may form cycles. Each node ...
0
votes
0answers
14 views

Parent Node in BST

Is it a good idea to store a pointer to the parent node in a binary search rather than to find the parent node several times? ...
0
votes
2answers
40 views

Comparing the efficiecy of 2 run times

I have a heap with $n$ elements. $k$ represent a number that is the height of one of the elements in the tree. I need to compare two run times and prove what i claim. The 2 run times are: $$ (1)O(...
0
votes
2answers
33 views

Findind The n/lgn intermidiate values in an unsorted array with asymptotic run time of $\Theta(n)$ SELECT algorithm

Let $A[1..n]$ be an unsorted array, we want to find the $n/lgn$ intermidiate numbers in the array. Namely the $(n/2)+1$ biggest number and the $(n/2) + 2$ biggest number and so on... until the $(n/2)...
-1
votes
1answer
64 views

reordering a max heap that the values of one of her subtrees has been changed

Let $H$ be a max binary heap with $n$ elements (vertexes). Pick a vertex $z$ in the heap with height of $k$ ($0<k<\lg n$) To every element in the sub heap of $z$ we add the constant value $c &...
0
votes
2answers
80 views

Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$

I have a min heap. I need to find the 7'th biggest value in the heap with $O(1)$. I need to build the algorithm. I dont realy have an idea how to get to this efficiency. Help? Thanks.
0
votes
0answers
23 views

What's the best bucket fill algorithm in terms of efficiency? [duplicate]

I am looking for an algorithm that fills a given region of connected particular nodes in minimum time. I have tried using flood flow algorithm but it's too slow and inefficient for large array, it ...
3
votes
1answer
108 views

Dynamic Program to solve an NP-complete partitioning problem

I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!! Let $A = \{ a_1, a_2, ..., a_n \}$ be a set where $a_i \in \mathbb{...
1
vote
1answer
60 views

For $T(n) = 16T(n/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$

Define: $ \lg x = \log_2x $. Let $ f(n), g(n) $ be some non-negative functions. Define $ f(n) = \Theta (g(n)) $ if $$ \exists c_1,c_2 \in R\colon 0 < c_1g(n) \leq f(n) \leq c_2g(n) $$ I want ...
2
votes
2answers
60 views

Does the word "efficient" usually refer to polynomial time or polylogarithmic time?

This question is strictly about terminology. I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and ...
1
vote
0answers
23 views

Regex vs line by line read efficiency - general concept question

Say, I have a file that is somewhere between 10-20 pages long. I need to extract 10-20 pieces of information from it that I can fairly easily extract using a series of regex-es or by running code that ...
0
votes
2answers
67 views

To calculate how many times a certain year repeats itself in the calendar within a given year range

Let's say I have a year $Y$. I wanna know how can I calculate the number of times the calendar configuration of the year $Y$ repeats itself in the year range $[A, B]$. Is there any method to it ...
3
votes
1answer
737 views

Add edges to undirected graph to make connected and minimize longest path

I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the ...
0
votes
1answer
40 views

Is it true that for every genetic algorithm there exists a non-genetic algorithm that achieves the same results more efficiently?

And if it is not true, what are the problem classes or characteristics for which genetic algorithms are superior?
1
vote
0answers
37 views

Least computationally expensive bitwise addition

I am familiar with the oft-cited method of bitwise addition using XOR and left shift for the carry, applied recursively. I was wondering if this is the least computationally expensive way to achieve ...
3
votes
2answers
310 views

Algorithm for detecting overlaps

This is a real-world application, not a student assignment. Suppose a list of events of that have startTime and endTime, and ...
4
votes
0answers
64 views

Peculiar MCMC sampling problem

I have two random variables, X and Y, and Y is a positive real number. I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$. I could ...
0
votes
2answers
134 views

Figuring out when one algorithm will be slower than another algorithm [closed]

I'm studying for a computing exam and came past the following question on a past paper and need help with it. When would algorithm A be slower than algorithm B? Demonstrate your answer with the help ...
2
votes
1answer
599 views

Shortest path in a incomplete graph

I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
-3
votes
2answers
2k views

BigO time complexity of 3 nested for loops

I'm debating with a friend whether a particular function I wrote is $O(N^3)$ or $O(N \times M \times X)$ I believe it is the latter since all 3 variables differ in size. $N = 100, M = 50, X = 10000$ ...
4
votes
1answer
83 views

Calculating all products of $n-1$ factors when given $n$ factors

Let's assume we have an operator $$ \times: E^2\to E$$ of which we merely know that it is associative. Let's say a multiplication $e\times f$ always takes up a time of $M$ for all $e, f\in E$. We're ...
1
vote
1answer
52 views

How much does C# gain from its value types

C# makes an distinction between value types and reference types contrast to Java where all (except primitives types) are of reference semantics. The design decision, as I understand it, is mainly to ...
0
votes
1answer
195 views

In which order to solve subproblems when using memoization?

I am currently trying to solve a task with memoization. I have following recursion: A (i, j) = f( A (i, j-1), A (i-1, j-1), A (i-1, j + 1) ) I am not sure in which order the sub-problems should be ...

1
2 3 4 5 6