Pulkit Chhabra

Time Complexity Analysis Using Recurrence Relations

As I already stated, the formulas shared don't always work, because, many times, the time/space used varies from one recursive call to another, based on the input. But, to our rescue, comes another way i.e. using recurrence relations to analyse time/space complexity for recursive functions.

Recursion: Time & Space Complexity Analysis - 2

In this article, we'll take the example of a problem that we've already solved in a previous article. Why? The honest answer is because I feel like doing it xD The more curated answer - I think it'll help in giving you an understanding

Recursion: Time & Space Complexity Analysis - 1

To understand the time & space complexity analysis, let's first go back and do as our home minister would say, understand the chronology first. What I mean is to recall/understand in what order and how are the recursive calls made. This will help us understand the difference

Find Whether a Given Integer is a Power of 3: Power of Three

Okay, as promised, 1 last problem before diving into the time & space complexity part. Power of Three Solve This problem, also, is a straightforward one. We'll be given an integer n, which can be positive as well as negative as well. Our target is to check whether

Fast Exponentiation Algorithm: Efficient Power Calculation Explained

Let's try a couple of more problems before moving on to the time & space complexity part properly. Will learn about how to calculate pow(x, n) efficiently in this article, and will solve 1 more in the next article. We'll do some informal thinking about

Most Asked Recursion Practice Problems with Solutions

In this article, let's solve a few beginner-level problems. The hope is to make recursion steal your heart xD Print N to 1 without loops Solve The problem is as simple as it gets. Given a value of N, the target is to simply print the values from

Getting a Hang of Recursion

Let's try to understand this using an example. Let's say, given a number N, we'd like to write code for finding the factorial of N. Of course, there is an iterative way to do so, as can be seen below: int factorial(int n)

Introduction to Recursion - Understand Recursion by Examples

Intuition What's recursion? It's magic. What if we ask google? No doubt, it gives us a reasonable answer. But also plays with us by writing "Did you mean: recursion" which is basically an infinite loop xD But what exactly is it? Imagine sleeping and

more-articles-dsa

Coming soon..

Hold tight! our team is working on more articles. We're constantly trying to bring a few new articles every week.

Java More Articles

Coming soon..

Hold tight! our team is working on more articles. We're constantly trying to bring a few new articles every week.

More Articles

Coming soon..

Hold tight! our team is working on more articles. We're constantly trying to bring a few new articles every week.

Multi Dimensional Arrays in C++

Introduction Linear 1D arrays are all fine, but you'll understand with experience (maybe you already do) that they're not enough. Maybe, instead of just storing the marks for a single subject of 30 students, you want to store marks that those 30 students have scored in

Quiz: Vectors

#include<bits/stdc++.h> using namespace std; int main() { vector<int> v; for(int i = 1; i <= 17; ++i) v.push_back(i); for(int i = 1; i <= 12; ++i) v.pop_back(); for(int i = 1; i <= 3; ++i) v.push_back(

Vector Implementation - 2

The slippery road is mostly over, the journey of vectors will be a bit smoother from now on. The pop_back() function If the user wants to get rid of the last element of the vector, let's reduce the size by 1; that's it! Also, for

Vector Implementation - 1

Brainstorming Let's try to think about this problem logically. Of course, the problem is that we don't know the number of elements to be pushed in the array beforehand; how do we design a data structure to tackle this problem and let the user push/pop

Vector Basics

Introduction Hi folks, I'm writing this one a few days after the last one as I was busy meeting MS Dhoni at an event 😉. Coming to the point now, vectors! Why did the vector get invited to the array's party? Because it knew how to dynamically

Quiz: Arrays Theory

#include<bits/stdc++.h> using namespace std; int main() { {int arr[5] = {};} cout << arr[1]; return 0; }

Caveats in C++ Arrays

Introduction So far we've learnt 1 way to declare an array and covered some related aspects related to that. In this article, we'll answer a few more things like: 1. What exactly is this stack memory? 2. Is there any other way of creating an array?

Arrays Memory Allocation in C++

Introduction Almost all of the runtime data of a C++ program is stored in RAM. More specifically, if I talk about arrays that we declare/initialise using the way we just learned, and if we do it inside a function, their data is stored in something called the stack memory

Time and Space Complexity

Quiz: Time Complexity

No talking here, only testing. int Sum1ToN(int n) { int ans = n*(n+1)/2; return ans; } int getSum(int n, int m) { int ans = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) ans++; return ans; } int doRandomStuff(int n, int

Time and Space Complexity

How to Calculate Time Complexity?

To calculate Time Complexity, we must try to understand the code line-by-line and see how many operations it will have to do for a given set of inputs. After finding the approximate number of operations as a function of the input variable: 1. Get rid of those terms that will

Time and Space Complexity

Comparing Different Time Complexities

In this article, I'll try to give you folks a brief idea about how much time codes with different time complexities take to run when given different sizes of inputs. Before diving in, I'd like to share that a C++ code can run around 2∗108

Time and Space Complexity

Different Notations in Time Complexity

Now that we know, on a high level, what time & space complexities are, it's a good time to look at different ways to represent them and try to make sense of them practically. Let's clear out the make sense of it part right now. It&

Time and Space Complexity

Introduction to Space Complexity

Alright; after having understood time complexity, this should be fairly easy. We just learned that measuring time efficiency in terms of the absolute time it takes to run a code is not ideal. Similarly, we can't just say that the space complexity of a program is 73 bytes

Time and Space Complexity

Inroduction to Time Complexity

Why did the algorithm go to therapy? It had an issue with time, and needed a safe space to sort it out! If I ask you, how time-efficient is this code you've written? What do you think will be the right way to measure it? What if you