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
1 answer
26 views

what is the time complexity of this while loop nested in a for loop?

I'm really having rough time understanding the time complexities of nested loops. So, please help me out in this code. The code is on sliding window with changing length: ...
1 vote
4 answers
3k views

Time complexity for concatenating strings

I was going through this piece of code from an algorithms books and something doesn't look clear Please ignore the spelling errors, How does 0(x + 2x + nx) reduce to o(xn^2) ? My analogy, assuming ...
1 vote
1 answer
36 views

Tight analysis on a custom data structures with Insert and Remove-Min

I have a data structure supporting the operations Insert(X) and Remove-Min(). Remove-Min() ...
0 votes
1 answer
18 views

Landau Notation/Big O notation

In our class the following exercises/examples were given: Compute/find $n_0$ and c from the formal definition of each Landau symbol to show that: $n^{2/3} \in \Omega(log^8(n))$. Then in the Solution ...
1 vote
1 answer
26 views

Are there any "fast" algorithms for defragmenting memory?

This is about memory, not files or filesystems. So in a typical process, imagine you have a string "Hello world" that later gets changed to "Hello". Or a list of 100 objects later ...
-4 votes
0 answers
30 views

Whats the big O notation of the following code?

int j , f; System.out.println("enter a number"); ...
0 votes
1 answer
59 views

How to resolve the clash between definition of Big O notation and Inductive Hypothesis when proving running time by substitution method?

Suppose you have to prove the solution to the following recurrence by Induction, $$ T(n)= \begin{cases} \Theta(1), & n=1 \\ 2 T(\lfloor n/2 \rfloor)+\Theta(n), & n>1 \end{cases} $$ Here, $\...
0 votes
1 answer
65 views

Complexity of multiple $O(\log N)$ is $m*O(\log N)$ or $O(\log N)$?

Assume we have an algorithm consists of several (assume m and m<10) different algorithms each of which has time complexity $O(\log N)$. Is the time complexity of our algorithm is $m*O(\log N)$ or ...
0 votes
1 answer
28 views

How to show that $n^2 = O(f(n-1)+n)$?

This is from Ex. 0.2.(b) from "Computational Complexity" by Arora and Barak (2009): One needs to find a non-recursively defined function $g$ s.t. (1) $f = O(g)$ and (2) $g = O(f)$, where $f(...
0 votes
0 answers
31 views

Baby step giant step algorithm complexity calculation

My question here is mainly a way for me to understand complexity a little better by a confusing example. From what I understand of calculating the complexity of an algorithm, we take the number of bit ...
0 votes
1 answer
42 views

Big O- and Omega-Notation for functions

I want to find out how to check, if the following relationships are true or false. f(n) = nlog(n!); g(n) = nlog(2n^3n); Check, if f(n) = O(g(n)) and/or f(n) = Ω(g(n)) true/false; f(n) = 3n^2; g(n) = 9^...
-1 votes
1 answer
73 views

Find the values for n0 and the constant factor c such that f(n) = n log n is Ω(n)

I was recently introduced to big O and big Omega, as well as big theta. I know that big O is the worse case scenario in terms of runtime, big Omega is the best case scenario, and big theta is in ...
1 vote
0 answers
26 views

Does creating an array count as a primitive operation under the RAM model?

int[] arr = new int[10]; Would this count as a single primitive operation under the RAM model or would it be 10 operations as we are allocating 10 memory locations ...
1 vote
1 answer
93 views

Subtraction on Big Theta notation

This is a question I got for an assignment, and I have been stuck on it for the past few days. Prove that $\Theta(n)+\Theta(n-1) = \Theta(n)$ Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$ I ...
0 votes
4 answers
58 views

Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?

So I'm doing an AI course that is talking about time complexities of different tree search algorithms. On this slide it talks about the time complexity of the algorithm, and I'm confused as to why we ...
0 votes
5 answers
125 views

Prove big O notation for $\log(n!)$ without applying Stirling's formula

I want to prove that, $$ \log n! \in O(n \log n) \land \log n! \in \Omega(n \log n)$$ The straightforward approach is to apply Stirling's formula but I am looking for a different path to follow. Can ...
0 votes
2 answers
95 views

Big O notation: how to prove $4\sqrt{n} + 2n\log_2(n) + 3 = \mathcal{O}(n\log(n))$?

I'm following an online course about Complexity and I'm learning a lot of stuff. I came across a particular exercise and I'm unable to find it out by myself, this is why I'm writing this message here. ...
0 votes
1 answer
45 views

sort is equal to inversions logic

In Bubble sort, the number of swaps/comparisons is equal to the number of inversions. 1st pass it will do (n -1) comparison 2nd pass it will do (n-2) comparison....so on (n-1)n = n^2 - n Worst case ...
-1 votes
1 answer
39 views

Complexity of T(n)=2T(n-1)

I built a recursion tree like this: 0 / \ 0 0 /\ /\ ... ... So the tree has height n, and width $2^n$. But if the sum of all levels is $\sum_{i=0}^{n}...
1 vote
3 answers
127 views

Θ, O and Ω, and how they relate to each other as subsets

I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track. I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
1 vote
3 answers
78 views

Help with model answer for time complexity

Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n? I tried to write this in python to ...
0 votes
2 answers
49 views

A little confusion with Big Theta time complexity

I came across one Big Theta expression: Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way. As per definition of Big Theta.. any function ...
1 vote
1 answer
83 views

How to find parameter sets for a big-O expression to be fixed-parameter tractable?

I've been stuck on the following assignment taken from Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis: Imagine that the following big-O expressions ...
0 votes
2 answers
458 views

Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G. My algorithm is as follows: Generate all subgraphs of size k, and check ...
1 vote
3 answers
58 views

Difference between an exact and Big O Notation for worst case runtime

I'm having a problem with an exercise, I'm supposed to calculate the exact worst case runtime and the worst case runtime in Big O Notation for a given algorithm. This is what I'm struggling to ...
1 vote
1 answer
234 views

Time complexity when taking certain elements and iterating over them?

I'm trying to gain a better understanding of Big O. Here is something that I'm unsure about. Say we have an array containing N elements that is inputted by the user. From my understanding iterating ...
0 votes
2 answers
95 views

Quicksort with insertion sort

Okay so I have implemented quicksort with insertion, where K is a value until which the recursion occurs and then rest of the array is sorted using insertion sort. Now I am comaparing 3 different ...
-2 votes
2 answers
46 views

What is the BigO of a C# function when runtime is 3n - logn + 1

I am trying to learn notations for a course and I am stuck on how to even start. I need to figure out the BigO for this function. Question is there's a C# function bool isPalindrome(string S) which ...
3 votes
2 answers
316 views

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

Given the recurrence $$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$ My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
1 vote
1 answer
48 views

Simplifying Notations in Recurrence Relation

In the CLRS book, section 4.4 they try to resolve the following recurrence: $$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$ Later, they write the same recurrence as $$T(n) ...
0 votes
1 answer
60 views

Understanding time complexity of algorithm to determine if parenthesis are matching

Both these algorithms determine if all the parenthesis in a string are balanced and properly nested. The first algorithm uses "a constant amount of memory, regardless of the length of the string.&...
2 votes
3 answers
77 views

Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?

The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says ...
2 votes
3 answers
179 views

Determining Big O of a for loop nested within a while loop

I apologize if this question is a duplicate as i cannot find a similar question in this community forum, please comment the post in which this may be a duplicate of so i can update this post :) Im a ...
1 vote
1 answer
92 views

Why do hash tables have no access/indexing complexity but have $O(1)$ search complexity?

Sources: https://en.wikipedia.org/wiki/Best,_worst_and_average_case https://www.bigocheatsheet.com/ It can be seen that a Hash Table has no access/indexing complexity given the above sources. This ...
1 vote
1 answer
32 views

Comparing two functions rate of growth

This is pretty simple and I THINK I know the answer to the question, but I don't know how to prove it formally. Below follows the question. Question. Compare the functions $f(n) = \frac{n^2}{\log(n)}$ ...
-2 votes
2 answers
57 views

Prove $n\log n\neq O(g(n))$ where $g(n)$ alternates between $\log^*n$ and $n!$

I have to prove that $f(n) \neq O(g(n))$, where $f(n) = n\log n$ and $g(n)$ is $\log^*n$ if $n$ is odd and $n!$ if even. So my thought is to say that $f(n) = O(g(n))$ and then with the definition ...
2 votes
1 answer
55 views

Which approach of mine for an algorithm upper bound is correct?

Say we have this algorithm in Python. ...
1 vote
1 answer
42 views

Newbie needs some explanation on the following code and O-expressed time complexity

I am learning data structures and algorithms currently, and want to understand how the following codes received their O-notations. Code example #1: ...
0 votes
1 answer
41 views

Possible Error in TAOCP

In section 1.2.11.2 of Donald Knuth's first volume of TAOCP, he gives an exercise at the end to prove that $g(n) = \Omega (f(n)) \iff f(n) = O(g(n))$ (exercise 13). His solution is simply: "we ...
-1 votes
2 answers
85 views

Which is larger: $n^{3/2}$ or $n^{\log n}$?

We know that $f(n)$ is $\mathcal O(g(n))$ if $\exists c\ge0$ s.t. $$\lim_{n\to\infty}\dfrac{f(n)}{g(n)} = c.$$ Let $f(n)=n^{3/2}$ and $g(n)=n^{\log n}.$ When I am applying L'Hôpital's rule for $$\...
7 votes
3 answers
3k views

What are you allowed to move into the big O notation for it to be still correct?

Can someone tell me what the rules are for moving log or exponents into the $O(n)$ notation so it is still correct? For example: Is this $\log(O(n))= O(\log(n))$ correct? Or is this correct $O(n)^2=O(...
2 votes
2 answers
70 views

Does $f(n) \in O(g(n))$ imply $2^{f(n)} \in O(2^{g(n)})$?

Is the following true: $$ f(n) \in O(g(n)) \text{ then } 2 ^ {f(n)} \in O(2^{g(n)})$$
2 votes
3 answers
96 views

$\log_{2}{(\frac{1}{2}n)} + \log_{2}{(\frac{1}{4}n}) + \log_{2}{(\frac{1}{8}n)} + \ldots + \log_{2}{(\frac{1}{2^{log_{2}(n)}}n)} = O(\log_{2}(n))$?

I am trying to analyze a series that I found, in the analysis of an algorithm. And I was wondering if the following was true: $$\log_{2}{\left(\frac{1}{2}n\right)} + \log_{2}{\left(\frac{1}{4}n\right)}...
2 votes
1 answer
93 views

best and worst case number of key comparisons of an algorithm

Consider the following algorithm: ...
4 votes
1 answer
378 views

Big O vs. Big Theta for AVL tree operations

On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big ...
1 vote
1 answer
84 views

Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method

Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$. I tried to form the Induction Hypothesis but didn't succeed in choosing the right one. Try 1: If we ...
1 vote
1 answer
27 views

How can we assume the asymptotic complexity of 1/2n^2 - 3n

I am trying to understand how asymptotic complexity of the given function is calculated based out of Introduction to algorithms by Thomas Cormen. In the book we are trying to solve inequality for $f(n)...
1 vote
2 answers
45 views

Calculating Big O if unknown runtime of called functions

I haven't been able to track down if there is a generally accepted practice for assigning a Big O value when dealing with functions of unknown runtime. Given the following pseudocode, with two ...
1 vote
1 answer
53 views

What would be the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$?

What is the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$? I was thinking that the lower bound would simply be $\omega(n) = cn^2 + n$, for the constant $c = 3$ and integer $n \ge 1$. Indeed, $...
1 vote
1 answer
58 views

Whether and how to distinguish two kinds of $O(1)$ speedup

Here is a very bad algorithm that computes $4n$ for an integer input. ...

1
2 3 4 5 6