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
0 votes
2 answers
26 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
  • 167
1 vote
1 answer
39 views

Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
john doe's user avatar
  • 167
0 votes
1 answer
34 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
  • 21
1 vote
0 answers
10 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
33 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
34 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
61 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
34 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
3k 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
47 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
103 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 ...
just_learning's user avatar
1 vote
3 answers
97 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 ...
pod's user avatar
  • 117
-1 votes
3 answers
55 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
65 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 ...
Zeeshan ahmed's user avatar
-1 votes
1 answer
69 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
29 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
67 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
45 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
160 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
92 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
62 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
58 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
33 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
44 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
392 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
215 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
43 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
234 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
38 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
65 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
37 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
85 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
52 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
82 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
45 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
238 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
0 votes
2 answers
66 views

Derive complexity from recurrence relation

On the Wikipedia article on Karatsuba algorithm (https://en.wikipedia.org/wiki/Karatsuba_algorithm#Time_complexity_analysis) it is stated: $T(n) = 3 T(\frac{n}{2}) + cn + d$ And then, by invocation of ...
Weier's user avatar
  • 181
0 votes
3 answers
68 views

Help understanding the proof of the definition of Big-Theta based on limits

I was reading Kleinberg's and Tardo's book (especifically, this one) and, on page 38, these authors define the Big-Theta notation the following way: Let $f$ and $g$ be two functions that $\lim_{n\to\...
OldCrow's user avatar
0 votes
2 answers
131 views

Confusion about asymptotic notations in math and computer science

The last times i was searching a lot to understanding Big O notation or in general asymptotic notations concepts because i didnt hear about it or them before starting studying in computer science. (...
Htam's user avatar
  • 3
0 votes
1 answer
33 views

How can it be formally proved that $f \in O(⌊f ⌋)$

I'm trying to prove that $f \in \mathcal{O}(\lfloor f \rfloor)$ given that $\forall m \in \mathbb{N}, f(m) \geq 1$ Here's what I've thought of so far, we can set C = 10 and k = 1 and somehow prove ...
Raghav Sinha's user avatar
1 vote
3 answers
97 views

Upper bounding this expression

I need to prove that the following expression is $\mathcal O(n \log n)$ with the substitution method: $$ T(n) \leq 3\log n + n + \frac{6}{n}\sum^{n - \frac{\log n}{3}}_{i=\frac{\log n}{3}} T(i)$$ This ...
joeren1020's user avatar
1 vote
1 answer
75 views

Proving this recurrence is $n \log n$

I need to prove that $T(n)$ is $\mathcal O(n\log n)$ with the substitution method. $$ T(n)\leq 3\log n + n + \frac{6}{n}\sum^{2n/3}_{n/3}T(i).$$ This is my attempt: I assume $T(n) \leq c n \log n$ and ...
joeren1020's user avatar
1 vote
0 answers
51 views

Runtime of this algorithm

I have an algorithm with running time that satisfies $$ T(n) \leq n + \frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n-i)),$$ and $T(0) = 0$. I was able to show that $T(n) = \mathcal O(n\log n)$ with a leading ...
Keio203's user avatar
  • 257
0 votes
1 answer
132 views

search for the next prime number more efficiently?

...
ant0982's user avatar
  • 13
0 votes
1 answer
44 views

Understanding why this upper bound is tight

Consider an algorithm with the following recursion $$ T(n) \leq T(n/3) + T(2n/3) + \mathcal O(n)$$ for its running time. I understand that $T(n) = \mathcal O(n \log n)$ by drawing the recursion tree ...
Keio203's user avatar
  • 257
0 votes
2 answers
99 views

Asymptotic Relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$

What is the asymptotic relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$? The answer here mentions that both functions are $O(1)$ (because they are always $\leq 1$) but not $\Omega(1)$ (because ...
20210352's user avatar
0 votes
1 answer
566 views

Why is the complexity of BFS O(V+E) instead of O(V*E)?

CLRS pseudocode: ...
mimmolg99's user avatar
1 vote
1 answer
81 views

Why not $O(n^{\log_ba})$ for case 1 of the Master Theorem instead of $O(n^{(\log_ba) - \epsilon})$?

Someone who was explaining to me the master theorem said that for the case 1, we compare the $n^{\log_b(a)}$ and $f(n)$. If the growth rate of $n^{\log_b(a)}$ is greater than the growth rate of $f(n)$ ...
Mina's user avatar
  • 113

1
2 3 4 5
7