Questions tagged [big-o-notation]

Big O Notation is an informal name of the "O(x)" notation used to describe asymptotic behaviour of functions. It is a special case of Landau notation, where the O is the Greek letter capital omicron. Please consider using the [landau-notation] tag instead if your question is related to small omicron, omega, or theta in Landau notation.

Filter by
Sorted by
Tagged with
2 votes
2 answers
97 views

Time Complexity O-Notation for Kociemba, Korf, and Thistlethwaite's Algorithms? (Rubik cube)

I'm currently studying the 3x3x3 rubik-cube-solving algorithms developed by Kociemba, Korf, and Thistlethwaite and I'm interested in understanding their computational complexities. Could someone ...
Lisa's user avatar
  • 23
0 votes
1 answer
26 views

Solving recurance relation with master theorem

I'm studying asympotic analysis and I encountered this problem: Given a recurrence relation: $$T(n)= aT(n/b)+cn^a (n>0;a>=1;b>=1)$$ prove that if $a>a^b$ then T(n)=$\mathfrak\theta(n^{...
hải nguyên đỗ's user avatar
0 votes
1 answer
84 views

what is the complexity of this sorting algorithm?

...
Moh's user avatar
  • 49
7 votes
1 answer
582 views

Possible Mistake in Skiena's Algorithm Design Manual

In Skiena's book Algorithm Design Manual, 3rd Edition, it is claimed on page 45 that $$ mn - m^2 + m \in \Omega(mn) $$ where $m,n \geq 0$ and $m \leq n$. I claim that this is in fact false, with the ...
Joshua's user avatar
  • 173
1 vote
0 answers
87 views

What is the difference between $O$ and $\widetilde{O}$?

We know that $\widetilde{O}(f(n))$ — $O$ with a tilde above it — which means $O(f(n) \text {polylog}(f(n)))$, i.e., $O(f(n) (\log f(n))^k)$ for some $k$. Also I have seen in Wikipedia that $n2^n=\...
A. H.'s user avatar
  • 498
1 vote
2 answers
149 views

What is the Time Complexity of this Slow Sorting Algorithm?

...
Moh's user avatar
  • 49
2 votes
2 answers
61 views

Big O notation of $O(n/(m-n))$

I'm new to the complexity theory and have a basic question about the big-O notation that I encountered. I came across a complexity of $O\big(\frac{n}{m-n}\big)$, where both $n$ and $m$ are independent ...
user185671631's user avatar
0 votes
0 answers
41 views

Calculating Runtime Complexity: Recursion + Memoization vs Dynamic Programming (with example)

For cases where recursion is used as well as memoization (so that a number of subtrees of what would otherwise be the overall recursive call tree are each replaced to be ...
mishar's user avatar
  • 101
1 vote
1 answer
30 views

Big O, Understanding when the increment is doubling

I am trying to find the Big O notation of this code below, really its the big theta, but whatever I believe its the same in this case. ...
Kuro's user avatar
  • 15
0 votes
1 answer
55 views

Big O Notation, Why do we ignore everything inside the log?

Okay, so I understand implicitly why we might write f(n) = log 3n = O(log n) but I don't really understand why lets say ...
Kuro's user avatar
  • 15
-1 votes
2 answers
77 views

Adding O(x)+O(x-1)+O(x-2)+

I have a function $f$ such that is the sum of big O terms, such as $$f=\left[\sum_{i=1}^x \frac{1}{i}\right] +O\left(\frac{\ln^4 x}{x}\right)+O\left(\frac{\ln^4 x-1}{x-1}\right)+O\left(\frac{\ln^4 x-2}...
fox's user avatar
  • 183
2 votes
1 answer
33 views

Expected number of mistakes grows logarithmically in number of iterations - improving performance?

I am reading a paper (link) in which an algorithm proposes a solution $\hat{\mathbf x}^{(t)}$ in each iteration $t = 1, \dots, T$, and each time, learns the true solution $\mathbf x^{(t)}$, so we ...
caitlin's user avatar
  • 21
0 votes
2 answers
74 views

Time complexity of algorithm involving function calls

Me again. This time I have a more general question. Suppose I have the following code snippet: ...
john doe's user avatar
  • 177
1 vote
1 answer
169 views

Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
john doe's user avatar
  • 177
0 votes
1 answer
59 views

Find a substring length $k$ with maximum occurrences

Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string. We want $O(S)$ time complexity in an average case. I think the solution lies in sophisticated ...
popcorn's user avatar
  • 183
1 vote
0 answers
26 views

Auxiliary Space Complexity of Dictionaries whose Keys are Iterables of Variable Size

Recently, I began delving into complexity analysis with dictionaries. More specifically, I have been looking at auxiliary space complexity. For the most part, this type of analysis has been ...
LateGameLank's user avatar
0 votes
1 answer
62 views

Struggling with Recurrence Relation using Telescoping Approach

I have the following recurrence relation that I am trying to solve using the telescoping approach: $T(n) = \begin{cases} T(\frac{n}{4})+ n^2 & \text{for } n \geq 4 \\ 1 & \text{otherwise} \...
Nancy Drake's user avatar
0 votes
0 answers
66 views

Ranking functions by order of growth

Did I correctly rank these functions by order of growth? I ranked them from smallest to largest (left to right). I have to eventually prove this ranking, so just looking to make sure that I have the ...
Jeremy Bowens's user avatar
0 votes
1 answer
71 views

Why, for $f(n) = n \cdot \sqrt n$ and $g(n)=n^2/\log n$, we have $f(n) = o(g(n))$?

Let $f(n) = n \cdot \sqrt n$ and $g(n)= \frac{n^2}{\log n}$. Why is $f(n) = o(g(n))$? Could you please explain to me why this is so? I have tried l'Hôpital's rule but it doesn't add any ...
kjkjkjkjkj's user avatar
0 votes
1 answer
37 views

Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?

Which function grows faster: $$f(n) = 4^{n^2 \log_2 n} \text{ or } g(n) = (n!)^n$$ Which is true? $f(n) = O(g(n))$ $g(n) = O(f(n))$ i.e., $f(n) = \Theta(g(n))$ none of the above? For lower values of ...
Kong's user avatar
  • 1
5 votes
5 answers
4k views

Time Complexity of Linear Search vs Brute Force

I am currently watching the FreeCodeCamp Algorithms and Data Structures Tutorial. In the explanation for exponential time complexity, they explain that using a brute force attack on a combination lock ...
jacoboneill2000's user avatar
0 votes
2 answers
50 views

From these functions, how to determine which grows faster without graphing?

How are you intuitively able to tell the Big-Oh of the functions and what order they are on? $$f(n)=3^n$$ $$g(n)=5^{3log_3{n}}$$ Note this is $5$ raised to $3log_3n$ $$h(n)=1024^{log_2n}$$
Stewart Jean's user avatar
0 votes
3 answers
109 views

How to get a time estimation of an O(n) function to modern multi-core CPU time?

How to get an estimation of an O(n) function to modern multi-core CPU time? For instance, how can I find the time it takes to run an algorithm in a 4-core/8-core CPU when I know its O(n) ? I searched ...
student's user avatar
  • 135
1 vote
3 answers
100 views

Is $n^{1.03} = \Omega(n \log \log n)$?

We had this problem on our Algorithms final. It threw me off because if $\log$ is $\log_2$ then graphing the function shows this is not true, but if $\log$ is $\log_{10}$ then it looks like it is. How ...
big-Oaf's user avatar
  • 117
-1 votes
3 answers
65 views

Can anyone help explain why the time complexity for this is O(n)

So ive already tried lookig at it but i just get O(nlogn) which is not correct there were some clues like using a geometric series where 1/2+2/4+3/8+i/2^i<2 but idk how to implement that what ...
Guest's user avatar
  • 1
0 votes
2 answers
72 views

Subtracting Two same asymptotic values

I am dealing with two values $a$ and $b$ such that they grow at the same asymptotic rate, i.e., $O(\frac{1}{\sqrt{N}})$. I want to achieve a reasonable bound for the difference $a - b$. When I go into ...
Zee's user avatar
  • 243
-1 votes
1 answer
85 views

Verify $n\log n=\Theta(10n\log10n)$

How do I Verify that $n\log n=\Theta(10n\log10n)$ I think I need to prove that there exists $c_1,c_2>0$ such that $c_1.g(n)\le f(n)\le c_2.g(n)$ Step 1 $$ \log n\le \log 10n\implies f(n)=n\log n\...
Sooraj S's user avatar
  • 139
0 votes
1 answer
47 views

Binary search calculating complexity big o

I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book : ...
LeoC's user avatar
  • 1
3 votes
0 answers
75 views

What's the fastest known non-galactic algorithm for matrix multiplication of large matrices

"A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in ...
blademan9999's user avatar
-1 votes
1 answer
47 views

Solve Recurrence Equation: 𝑇(𝑛)=𝑇(𝑛−4)+𝑛^2

I'm trying to practice recurrence equations, so I'm trying to solve this typology by unfolding method. I was wondering if what I write below was correct and obviously the result: $T(n) = n^2 + T(n-4) =...
emacos's user avatar
  • 121
0 votes
2 answers
218 views

When does Quicksort go from O(n log n) to O(n^2)?

Quicksort is O(n log n) average case, and O(n^2) worst case. The worst case occurs if one side of the pivot contains all of the elements and the other side contains none. However, I think the worst ...
TheSwiftTiger's user avatar
1 vote
2 answers
94 views

Given an array of size $n$, return a sorted array of floor($n^k$) elements for some $k<1$

We are given an array of size $n$ (it is not specified if we have an integer array, a specific range or any other assumptions), which might be unsorted, and a real number as a constant $k<1$. We ...
LearningSomeone's user avatar
0 votes
1 answer
93 views

Comparisons using Quicksort with the median as the pivot

Background Using a simplified Quicksort algorithm where the first element of the array is assigned as the pivot we get the following pseudocode for the algorithm: Quicksort($a$): (1) If length($a$) $...
FD_bfa's user avatar
  • 103
0 votes
0 answers
16 views

Need help verifying the complexity of an algorithm [duplicate]

I have the following algorithm which takes as an input a non negative integer n : i = n while i > 0 do : $\,$ $\,$ $\,$ $\,$i = i - 1 $\,$ $\,$ $\,$ $\,$j = 1 $\,$ $\,$ $\,$ $\,$ $\,$ $\,$ $\,...
pierrovoltela's user avatar
1 vote
1 answer
94 views

Finding max value in a min- heap

What is the time complexity of finding the maximal value in a minimum heap with n nodes? Can I assume the maximal value is in one of leafs? If yes, there are ceil n/2 leafs. Does that make the time ...
Sara's user avatar
  • 11
0 votes
1 answer
37 views

if f(n),g(n) =! 0 , for every n > 0 , and f(n) = Ω(g(n)) , then does this mean that 1/f(n) = O(1/g(n))

Basically what i am trying to prove is this : $f(n),g(n) \neq 0\quad , n>0 \ \ \ \ and f(n)=Ω(g(n)) \ \ \ , \ then \frac{1}{f(n)}=O(\frac{1}{g(n)}) $ I guess that if we take the definition of $f(...
pierrovoltela's user avatar
1 vote
2 answers
64 views

If we have f(n) ∈ O(h(n)) and g(n) ∈ Ω(h(n)), does that mean that f(n) + g(n) ∈ Θ(h(n))?

It is quite easy to prove that f(n) + g(n) ∈ Ω(h(n)), but I am having trouble with proving/disproving that f(n) + g(n) ∈ O(h(n)). Someone suggested that this question answers mine, which it doesn't. ...
figsinwinter's user avatar
1 vote
1 answer
469 views

Placing K gas stations among n cities to minimize distance

There are $n$ cities on a highway with coordinates $x_1$ , . . . , $x_n$ and we aim to build $K < n$ gas stations to cover these cities. Each gas station has to be built in one of the cities, and ...
Muffinlicious's user avatar
0 votes
5 answers
367 views

Is $n^n$ is a big-oh n factorial

Is it true or false that $n^{n} \in \mathcal{O}(n!)$ ? Any suggestions how to prove/disprove this statement?
taycants's user avatar
0 votes
1 answer
49 views

Trying to understand the time complexity of IDDFS

I'm trying to break down the Time complexity algorithm for IDDFS. Acknowledging that in general my understanding of maths is not that great. So I will be trying to talk things out. For BFS it is ...
Crocs123's user avatar
-1 votes
2 answers
322 views

If f = O(h) and g = Ω(h) then f+g is?

Is the answer O(h) or Ω(h) for f+g? My professor says its Ω(h), but I can't get it.
user159086's user avatar
0 votes
2 answers
64 views

Comparison between big-Ω and ω notations

Example of function f(x) such that it is true that f(x) = Ω(g(x)) but that it is not true that f(x) = ω(g(x))
emacos's user avatar
  • 121
0 votes
1 answer
39 views

Design an algorithm with linear complexity

Let A[1 : n] be a vector of n integers such that all elements except O(n^2/3) elements are between 1 and 10n. Design an algorithm with linear complexity that sorts A. Beyond the algorithm, what I can'...
emacos's user avatar
  • 121
0 votes
1 answer
78 views

Complexity of recursive function that calls itself with it's own return value

Given the following code: int f3(int n) { if(n <= 2) return 1; f3(1 + f3(n-2)); return n - 1; } I was trying to find the time complexity and I got this ...
complexity's user avatar
0 votes
1 answer
42 views

the size of nice tree decomposition

Recently, I am reading paper An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances, which use tree decomposition to give an upper bound for SAT resolution refutation. For a ...
Jxb's user avatar
  • 318
-3 votes
2 answers
103 views

How to find the standard theta notation of this?

Hi i am practising standard theta notation: How could i find the standard theta notation of the following : 2n + 3n^2(log n)^3 + 2 and ...
zeek's user avatar
  • 1
2 votes
1 answer
56 views

Finding general time complexity for recurrence relation $T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$

I was given an assignment in which I had multiple recurrence relations and I had to find their Big-oh time complexities. Nearly all of the recurrence relations were of the form as under: $$T(n)=aT(n/\...
Paras Khosla's user avatar
-1 votes
2 answers
126 views

How to prove this because if we consider big-oh than logn^2 <= log n + 5 can never happen if n grows?

f(n) = log n^2; g(n) = log n + 5 => f(n) = Θ (g(n)) I think we can prove this for omega but how can we prove it for Big oh ? because if we simplify it to logn + logn <= logn +5 => logn<=...
user157232's user avatar
0 votes
0 answers
48 views

Basic Clique Complexity Question

A question in a textbook says, suppose the regular Clique problem, which takes as input a graph G and a natural number k, and returns whether or not G has a clique of size >= k, can be decided in ...
Abhishek Manikandan's user avatar
0 votes
4 answers
808 views

What is the lower bound of n factorial

The upper bound of $n!$ is $O(n^n)$. But I am not getting a way to compute the lower bound of n!. We can write $n! = n\times(n-1)\times(n-2)\times\dots\times 1$. I can easily put all the terms as 1. ...
user529767's user avatar

1
2 3 4 5
8